Heute ist ein Beweis für P≠NP auf­ge­taucht und Infor­ma­ti­ker in aller Welt sind irgend­wie auf­ge­regt. Aber was bedeu­ten P und NP?

Ein­lei­tung

Ist ein Pro­blem in P oder NP? - das ist eine Frage von deren Ant­wort abhän­gen kann, ob die Berech­nung der exak­ten Lösung ein paar Stun­den dau­ert oder so lange wie das Uni­ver­sum alt ist. Ein Bei­spiel aus dem All­tag: Man will über den Tag ver­teilt noch einige Sachen erle­di­gen: Buch in der Biblio­thek abge­ben, was Essen, ein paar Sachen ein­kau­fen, sich mit jeman­dem tref­fen. All diese Dinge fin­den an ver­schie­de­nen Orten statt. Wie ist die kür­zeste Route von der eige­nen Woh­nung zu all die­sen Orten und wie­der zurück?

Die­ses Pro­blem ist das Traveling-Salesman-Problem und liegt in NP.

Wenn man (inklu­sive Wohn­ort) nur vier oder fünf Sta­tio­nen hat, sieht man die Lösung sofort, wenn man jedoch 20 ver­schie­dene Orte hat, die wild in der Stadt ver­teilt sind, gibt es über 100 Bil­lio­nen Mög­lich­kei­ten, und man sieht die Lösung nicht sofort. Alle Mög­lich­kei­ten durch­zu­tes­ten würde rela­tiv lange dauern.

Aber was wäre, wenn es trotz die­ser immen­sen Zahl einen Weg gäbe, die opti­male Route mit rela­tiv weni­gen Rechen­schrit­ten zu berechnen?

P und NP

P und NP sind Namen für Pro­blem­klas­sen. Grob gesagt ist P die Klasse der Pro­bleme, die sich auf einer nor­ma­len, d.h. deter­mi­nis­ti­schen, Rechen­ma­schine¹ in poly­no­mi­el­ler Zeit lösen las­sen. Genauer: Pro­bleme, die sich in poly­no­mi­ell vie­len Schrit­ten lösen las­sen. Bei­spiel: Eine gewisse Anzahl, nen­nen wir diese Zahl k, Per­so­nen trifft sich. Nun soll jeder jedem die Hand schüt­teln - wie viele Hände-Schüttelungen müs­sen durch­ge­führt wer­den? Es sind (k²-k)/2. Das run­den wir auf zu k². k² ist ein Poly­nom. Unser Hän­de­schüt­tel­pro­blem ist also in der Klasse P, weil nur es poly­no­mi­ell viele Schritte braucht.

Pro­bleme, die in P sind nennt man manch­mal salopp „effi­zi­ent lös­bar” - das meint man im Ver­gleich zu den Pro­ble­men in NP.

Die Klasse NP ist die Klasse der Pro­bleme, die sich auf einer nicht-deter­mi­nis­ti­schen Rechen­ma­schine in poly­no­mi­el­ler Zeit lösen las­sen. Das Wort nicht-deterministisch ist hier wich­tig und macht den Unter­schied zur Klasse P aus. Es bedeu­tet, dass unsere Rechen­ma­schine belie­big viele Berech­nungs­pfade erzeu­gen kann und es schon reicht, wenn einer davon erfolg­reich been­det wird. Das klingt irgend­wie ziem­lich unrea­lis­tisch und man müsste den­ken, dass man mit solch einer abge­fah­re­nen Maschine viel mehr Pro­bleme in poly­no­mi­el­ler Zeit lösen könnte, als mit der Maschine, auf der P auf­baut. Man würde also intui­tiv anneh­men, dass P≠NP, dass diese Klas­sen nicht gleich sind.

Beweis

Das zu bewei­sen sollte ein­fach sein - man muss ja nur ein Pro­blem fin­den, dass in NP liegt, aber nicht in P. Also ein Pro­blem, dass auf nicht-deterministischen Maschi­nen in poly­no­mi­el­ler Zeit lös­bar ist, auf nor­ma­len Maschi­nen jedoch nicht.

Das ist schwe­rer als man denkt, denn man muss nicht nur zei­gen, dass es für das Pro­blem aktu­ell kei­nen Algo­rith­mus mit poly­no­mi­el­ler Lauf­zeit gibt, son­dern man muss bewei­sen, dass es einen sol­chen Algo­rith­mus nicht geben kann.

Vinay Deola­likar hat das nun offen­bar geschafft, indem er, so wie ich das sehe, einen Zusam­men­hang zwi­schen der begrenz­ten Reich­weite von prä­di­ka­ten­lo­gi­schen Aus­sa­gen, phy­si­ka­li­scher Sta­tis­tik und der Pro­blem­klasse P auf­ge­deckt hat.

Mal sehen ob sich das bestätigt.

Update: Der Beweis ist wohl feh­ler­haft, aber an einer neuen Ver­sion wird gearbeitet.

Heute ist ein Beweis für P≠NP auf­ge­taucht und Infor­ma­ti­ker in aller Welt sind irgend­wie auf­ge­regt. Aber was bedeu­ten P und NP? Ein­lei­tung Ist ein Pro­blem in P oder NP? - das...