Wow, habt ihr euch die Zahlen notiert und verglichen?

Schon beim 5×5 Puzzle müssten wir 169 Millionen Jahre auf das Ergebnis warten. Selbst wenn jemand einen Supercomputer hat, der eintausend mal so schnell ist wie unser Computer – niemand hat Zeit so lange zu warten.

Deswegen wird das Katzenpuzzle als schweres Problem bezeichnet. Für ganz kleine Datenmengen (unsere Puzzleteile) lässt es sich noch lösen, aber wenn die Seitenlänge nur etwas größer wird, ist es schnell so kompliziert, dass wir so lange auf das Ergebnis warten müssten, dass es eigentlich nicht lösbar ist. Also mit doppelt so vielen Puzzleteilen benötigen wir nicht nur doppelt so lange, sondern sehr viel länger. Man sagt, „es skaliert nicht“.

Wenn ihr euch einen Algorhithmus überlegen „könntet", der für die doppelte Anzahl an Puzzleteilen nicht wesentlich länger als doppelt so lange benötigt, bekommt ihr 1 Million Dollar. Denn damit wäre das P-NP-Problem gelöst. Es ist eines der sieben Millennium Probleme, die das Clay Mathematics Institute im Jahr 2000 aufgezählt hat, und für die Lösung jeweils 1 Million Dollar bezahlt. Alternativ darf man übrigens auch mathematisch beweisen, dass es keine Lösung geben kann.