Bij een grote Rubikskubus is efficiëntie onvoorspelbaar

Praktische wiskunde

Net als bij het beruchte ‘handelsreizigersprobleem’ is bij een grote Rubikskubus een efficiënte oplossing niet vooraf te berekenen.

Doorgewinterde draaiers aan een Rubikskubus kunnen de beroemde puzzel, in 1974 uitgevonden door de Hongaar Ernö Rubik, in luttele seconden oplossen. De standaardkubus, met negen gekleurde vlakjes op elk zijvlak, kan vanuit elke toestand met hooguit twintig draaibewegingen worden opgelost. Voor grotere kubussen – met 16, of 25, of in het algemeen n2 vlakjes per zijvlak – wordt het maximaal aantal benodigde draaiingen groter. In 2011 bewees Erik Demaine dat het aantal draaiingen dat nodig is om een in de war gedraaide kubus met n2 vlakjes per zijvlak goed te krijgen proportioneel is met n2 gedeeld door de logaritme van n.

De grootste kubus: 17x17x17, oplossingsduur: 7,5 uur.
Of dit de efficiëntste manier is, is dus niet te berekenen.

Het is wiskundig niet moeilijk om een Rubikskubus in n2 / log n stappen op te lossen. Maar vaak moet het ook met minder draaiingen kunnen. Het hangt er vanaf in welke stand de kubus zich bij aanvang bevindt. De vraag is dan: kun je eenvoudig beslissen of een x aantal stappen toereikend is? Daarbij is x een of ander vast gekozen getal, veel kleiner dan n2 / log n.

Twee weken geleden wist Demaine het antwoord. Een methode om te bepalen of je een n × n × n kubus vanuit een of andere gegeven beginstand in x stappen kunt oplossen, bestaat hoogstwaarschijnlijk niet. Wat hij samen met zijn collega’s Sarah Eisenstat en Mikhail Rudoy bewees, is dat dit probleem dezelfde moeilijkheidsgraad heeft als het beroemde handelsreizigersprobleem, dat draait om de kortste rondrit langs een gegeven aantal steden. En dát is moeilijk, dat weten wiskundigen al jaren.

De Rubikskubus-verzameling van Gerwin Sturm. Foto Gerwin Sturm / Flickr

De categorie waar het Rubikskubusprobleem en het handelsreizigersprobleem in zitten, noemen wiskundigen ‘NP-problemen’. NP staat voor niet-deterministisch polynomiaal. De rekentijd om zulke problemen via trial and error op te lossen, groeit exponentieel naarmate de omvang van het probleem groter wordt. In het geval van het Rubikskubusprobleem is dat het aantal vlakjes per zijvlak, bij het handelsreizigersprobleem het aantal te bezoeken steden.

Beslissingsproblemen

NP-problemen zijn zogeheten ‘beslissingsproblemen’ met de eigenschap dat de (on)juistheid van een oplossing – hoe moeilijk die ook is om te vinden – heel makkelijk geverifieerd kan worden. Bij de Rubikskubus is dat duidelijk het geval: een vlugge blik op elk van de zes zijvlakken volstaat. Naar efficiënte methoden om NP-problemen op te lossen wordt al jaren gezocht, maar zonder succes. Daarom geloven de meeste wiskundigen dat dergelijke algoritmen niet bestaan.