Rubik’s Cube, kennt man. Kann man auch irgendwie lösen. Ich hatte als Kind nie einen und habe letztes Jahr meinen Jungs einen geschenkt. Wenn man sich ein bisschen reinfuchst dann bekommt man das Lösen dieses Teils nach Schema F auch hin. Jedenfalls bei dem Würfel mit der Kantenlänge n=3.

Es gibt allerdings auch komplexere Würfel mit größerer Kantenlänge n>3. Es ist irgendwie klar, dass die Lösung eines größeren Würfels komplexer ist als die eines kleinen. Aber wie viel komplexer eigentlich? Sowas beschäftigt gerne Mathematiker oder theoretische Informatiker. Grundsätzlich gibt es verschiedene Komplexitätsklassen für Probleme, und zwei davon sind von besonderem Interesse: Die Komplexitätsklassen P und NP. Zur Klasse P gehören die Probleme, die mit gängigen Rechnern in Polynomialzeit lösbar sind. Das sind die gutartigen Probleme, die man durch Totrechnen einfach in den Griff bekommen kann. Für Verschlüsselungen eignen sich dagegen eher die NP-komplexen Probleme, die man eben nicht einfach totrechnen können soll.

Zu welcher Komplexitätsklasse gehört nun das Lösen eines Rubik’s Cube? Dazu gibt es erstaunlich viele Arbeiten (z.B.: 1, 2, 3, 4). So wie ich das verstehe scheint das Finden einer optimalen Lösung eines Würfels ein NP-Problem zu sein, die gemeine Lösung  allerdings nur ein P-Problem.

Eigentlich wollte ich das alles gar nicht schreiben.
Eigentlich wollte ich nur dieses unglaubliche Video zeigen:

Der Kerl löst Würfel der Kantenlänge n=2, 3, 4, 5, 6 und 7 nacheinander in 6 Minuten und 23 Sekunden. So lange brauche ich fast für den 3er-Würfel…

Jetzt habe ich mir den Spaß gemacht und die Zeiten notiert, die er für die einzelnen Würfel braucht, und diese schließlich in Abhängigkeit der Kantenlänge geplottet:

Wenn man ein bisschen mit den Daten spielt ist schön zu sehen, dass für die Lösungsdauer sowas wie

$$ t \propto n^3 $$

gilt. Polynomial, also ein P-Problem. Ziemlich empirisch, das gebe ich zu… Trotzdem faszinierend, wie ich finde.