SAT Certificates for the Matrix-Multiplication Challenges over F2: All Ten `Expected-UNSAT` Instances Are Satisfiable, and a Type-3-Free Rank-23 Scheme

Stel je voor dat je een enorme, driedimensionale legpuzzel probeert op te lossen. Maar dit is geen afbeelding van een zonsondergang of een kat; het is een wiskundige machine die ontworpen is om twee rasters met getallen met elkaar te vermenigvuldigen. In de wereld van computerwetenschappen en wiskunde wordt dit "matrixvermenigvuldiging" genoemd. Decennia lang hebben wiskundigen gezocht naar de meest efficiënte manier om deze machine te bouwen. Ze willen weten wat het absolute minimum aantal kleine, basisbouwstenen (genaamd "vermenigvuldigingen") is die nodig zijn om het geheel te laten werken.

Beschouw deze bouwstenen als Lego-steentjes. Lange tijd wist iedereen dat we een 3x3 vermenigvuldigingsmachine konden bouwen met 23 steentjes. De grote vraag was: kunnen we dat ook met slechts 22? Om dat uit te zoeken, veranderden onderzoekers het probleem in een gigantische logische puzzel, vergelijkbaar met de puzzels die je in een videogame of een Sudoku-boek ziet, maar dan op een schaal die je duizelig maakt. Ze codeerden de regels van de wiskunde in een formaat dat computers kunnen controleren, waardoor ze een "SAT"-probleem creëerden (wat staat voor "Satisfiability" of vervulbaarheid). Als de computer een manier kan vinden om alle schakelaars op "aan" te zetten zonder de regels te breken, is de puzzel opgelost. Als de computer zegt "onmogelijk", dan zijn 22 steentjes misschien wel niet genoeg. Dit artikel duikt in een specifieke set van deze logische puzzels die ontworpen zijn om de grenzen van onze huidige computers en ons begrip van deze wiskundige machines te testen.

---

De Grote "Onmogelijke" Puzzel Die Dat Niet Was

Ontmoet Nick Palladinos, een digitale detective die besloot een frisse blik te werpen op een set van tien logische puzzels waar iedereen al de hoop in had opgegeven. Deze puzzels, bekend als de "Challenge 2"-instanties, werden gebouwd door andere onderzoekers met een zeer specifieke, rigide set regels. De makers van deze puzzels geloofden dat ze "onmogelijk" waren. Ze dachten dat de regels zo strikt waren dat geen enkele combinatie van 23 Lego-steentjes mogelijk in elkaar zou passen om de machine te bouwen. Het was also alsof je werd verteld: "Hier is een doos met een slot dat absoluut niet geopend kan worden," en iedereen knikte alleen maar en liep weg.

Maar Palladinos probeerde het slot niet simpelweg te forceren met een grotere hamer. In plaats daarvan keek hij naar het slot zelf en realiseerde hij zich iets cruciaals: de regels waren niet zo strikt als iedereen dacht.

De makers van de puzzel hadden de regels geschreven met "positieve" instructies. Ze zeiden: "Je moet dit specifieke steentje hier hebben," en "Je moet dat steentje daar hebben." Maar ze vergaten te zeggen: "En je mag geen andere steentjes tegen deze aan hebben." Het blijkt dat de wiskunde toestaat dat er extra steentjes worden toegevoegd, zolang de uiteindelijke machine nog steeds correct werkt. De "onmogelijke" puzzels waren eigenlijk gewoon in afwachting van iemand die zou beseffen dat de deur niet op slot zat; het was alleen dat iedereen probeerde de puzzelstukjes in een doos te passen die te klein was, waarbij ze negeerden dat de doos eigenlijk een beetje groter kon zijn.

De Magie van Verschuiven en Wisselen

Dus, hoe heeft Palladinos ze opgelost? Hij gebruikte een slimme truc waarbij "symmetrie" betrokken was. Stel je voor dat je een Rubik's Cube hebt. Als je de hele kubus draait of roteert, bewegen de kleuren rond, maar de kubus blijft hetzelfde object. Palladinos realiseerde zich dat de wiskundige "machine" die hij aan het bouwen was, een soortgelijke eigenschap had. Hij kon een werkende oplossing (een set van 23 steentjes die succesvol matrices vermenigvuldigen) nemen en de stukjes ronddraaien, roteren of herschikken met een speciale wiskundige dans genaamd de "GL(3, 2) groepswerking".

Denk aan het herinrichten van de meubels in een kamer. Je kunt de bank naar links schuiven, de lamp naar rechts en het tapijt in het midden. De kamer is nog steeds een kamer, en de meubels werken nog steeds, maar de indeling is anders. Palladinos nam een bekende, werkende oplossing en paste deze wiskundige "draaiingen" toe. Vervolgens gebruikte hij een matchingsspel om te zien of deze nieuwe, herschikte versies van de meubels in de specifieke "sleuven" pasten die vereist waren door de lastige puzzels.

En raad eens? Ze pasten perfect!

Sterker nog, Palladinos vond niet slechts één oplossing; hij vond oplossingen voor alle tien de puzzels die zogenaamd onmogelijk waren. Hij bewees dat deze "onoplosbare" formules eigenlijk vervulbaar zijn. De computer gokte niet alleen; hij controleerde elke regel. Het artikel bevestigt dat voor alle 10 deze "Challenge 2"-bestanden een geldige manier bestaat om de 23 bouwstenen te rangschikken om de machine te laten werken. Het "onmogelijk"-label was een misverstand van de regels, niet een echte wiskundige barrière.

De "Ghost" Brick en de Perfecte Oplossing

Het artikel pakte ook een derde uitdaging aan, "Challenge 3". Deze stelde een andere vraag: Kunnen we de machine bouwen met 23 steentjes, maar zorgen dat één specifiek steentje "geestachtig" is? In de wiskunde betekent dit dat een van de 23 bouwstenen een "type-3 count" van nul moet hebben. Dit is een chique manier om te zeggen dat een van de steentjes niet mag deelnemen aan een specifiek, veelvoorkomend patroon dat normaal gesproken in deze machines voorkomt.

Palladinos slaagde hier ook in. Hij begon met een werkende oplossing en voerde een kleine, precieze wisseling uit. Hij nam twee steentjes die een specifieke taak uitvoerden en verving ze door twee andere steentjes die exact dezelfde taak deden, maar er anders uitzagen. Deze wisseling was zo slim dat het een "ghost brick" creëerde—één die het verboden patroon helemaal niet activeert. Hij bewees dat je inderdaad de 3x3 matrixvermenigvuldigingsmachine kunt bouwen met 23 steentjes, waarbij één van hen volledig vrij is van dat specifieke patroon.

De Laatste Controle

Om er zeker van te zijn dat niemand kon zeggen: "Oh, je hebt gewoon geluk gehad met de computer," bouwde Palladinos een superstrikte checker. Hij genereerde de volledige lijst van 26.541 variabelen (de schakelaars) voor alle 21 puzzels (10 van Challenge 1, 10 van Challenge 2, en 1 van Challenge 3). Vervolgens draaide hij een apart programma dat de oorspronkelijke puzzelregels en de nieuwe oplossingen las, waarbij hij elke van de 2.461.316 logische clausules controleerde.

Het resultaat? Nul fouten. Elke regel werd voldaan. De oplossingen zijn echt, ze zijn geverifieerd en ze zijn reproduceerbaar. Iedereen met de juiste software kan dezelfde code draaien en krijgt binnen ongeveer negen seconden exact hetzelfde antwoord.

Wat Dit Betekent (en Wat Het Niet Betekent)

Wat is de grote les? Het artikel laat zien dat de "onmogelijke" puzzels eigenlijk altijd oplosbaar waren; de regels waren simpelweg niet zo strikt als de puzzelmakers dachten. Het is een herinnering aan het feit dat in wiskunde en computerwetenschappen de moeilijkste stap soms niet het vinden van de oplossing is, maar het beseffen dat het probleem niet zo kapot is als het lijkt.

Er is echter een addertje onder het gras. Dit artikel lost de puzzels op voor een specifiek type wiskundige wereld genaamd "F2" (wat vergelijkbaar is met een wereld waarin getallen alleen ronddraaien na 1, dus 1+1=0). Het bewijst niet dat we een machine met 22 steentjes kunnen bouwen. De zoektocht naar de 22-steentjes machine (Challenge 4) staat nog steeds open. Het artikel zegt ook niet dat deze oplossingen werken voor elke soort wiskunde die je in de echte wereld zou gebruiken, zoals de complexe getallen die gebruikt worden in de techniek. Het lost alleen de specifieke logische puzzels op zoals ze geschreven zijn.

Maar voor de puzzels die geschreven zijn, is de conclusie duidelijk: het "onmogelijke" is in feite mogelijk. De deur zat nooit op slot; we hadden alleen de juiste sleutel nodig om de klink om te draaien.