Eine Million Dollar Preisgeld
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.
Über den Kurs
Wir nehmen oft an, dass Computer eigentlich alles lösen können. Doch es gibt sehr viele Probleme, für die es sehr lange dauert, eine Lösung zu finden. Es gibt sogar einige, die so schwierig sind, dass es hunderte oder tausende Jahre dauern würde, sie zu lösen.
Das Katzenpuzzle sieht kinderleicht aus, gehört aber zu den besonders schwer zu lösenden Problemen. Löst es selbst und findet heraus, warum es für Computer gar nicht so leicht lösbar ist. Keine Sorge, ihr werdet sicher die Lösung finden – vielleicht sogar schneller als der Computer.
Lernziele
- Verstehen, was „schwierige" und was „leichte" Probleme sind
- Unterscheiden, was beim Lösen von Problemen die Limitierung von klassischen Computern ist und warum Quantencomputer hier in Zukunft helfen könnten
Zukunftskompetenzen
Durch unsere Lernformate vor Ort oder auf unserer digitalen Lernplattform vermitteln wir Zukunftskompetenzen. Besonders wichtig ist uns dabei: Nur wer auch wirklich lernt mit digitalen Werkzeugen, egal ob Soft- oder Hardware, umzugehen, kann eine digitale Zukunft auch aktiv mitgestalten anstatt diese nur zu konsumieren.
- Kritisches Denken
- Kritisches Denken