Heu­te 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?

Einleitung

Ist ein Pro­blem in P oder NP? - das ist eine Fra­ge 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 lan­ge wie das Uni­ver­sum alt ist. Ein Bei­spiel aus dem All­tag: Man will über den Tag ver­teilt noch eini­ge 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 die­se Din­ge fin­den an ver­schie­de­nen Orten statt. Wie ist die kür­zes­te Rou­te von der eige­nen Woh­nung zu all die­sen Orten und wie­der zurück? 

Die­ses Pro­blem ist das Tra­ve­ling-Sales­man-Pro­blem und liegt in NP.

Wenn man (inklu­si­ve Wohn­ort) nur vier oder fünf Sta­tio­nen hat, sieht man die Lösung sofort, wenn man jedoch 20 ver­schie­de­ne 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ür­de rela­tiv lan­ge dauern.

Aber was wäre, wenn es trotz die­ser immensen Zahl einen Weg gäbe, die opti­ma­le Rou­te 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 Klas­se der Pro­ble­me, die sich auf einer nor­ma­len, d.h. deter­mi­nis­ti­schen, Rechen­ma­schi­ne¹ in poly­no­miel­ler Zeit lösen las­sen. Genau­er: Pro­ble­me, die sich in poly­no­miell vie­len Schrit­ten lösen las­sen. Bei­spiel: Eine gewis­se Anzahl, nen­nen wir die­se Zahl k, Per­so­nen trifft sich. Nun soll jeder jedem die Hand schüt­teln - wie vie­le Hän­de-Schüt­te­lun­gen 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 Klas­se P, weil nur es poly­no­miell vie­le Schrit­te braucht.

Pro­ble­me, 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 Klas­se NP ist die Klas­se der Pro­ble­me, die sich auf einer nicht-deter­mi­nis­ti­schen Rechen­ma­schi­ne in poly­no­miel­ler Zeit lösen las­sen. Das Wort nicht-deter­mi­nis­tisch ist hier wich­tig und macht den Unter­schied zur Klas­se P aus. Es bedeu­tet, dass unse­re Rechen­ma­schi­ne belie­big vie­le Berech­nungs­pfa­de 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üss­te den­ken, dass man mit solch einer abge­fah­re­nen Maschi­ne viel mehr Pro­ble­me in poly­no­miel­ler Zeit lösen könn­te, als mit der Maschi­ne, auf der P auf­baut. Man wür­de also intui­tiv anneh­men, dass P≠NP, dass die­se Klas­sen nicht gleich sind.

Beweis

Das zu bewei­sen soll­te 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-deter­mi­nis­ti­schen Maschi­nen in poly­no­miel­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­miel­ler Lauf­zeit gibt, son­dern man muss bewei­sen, dass es einen sol­chen Algo­rith­mus nicht geben kann.

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

Mal sehen ob sich das bestätigt.

Update: Der Beweis ist wohl feh­ler­haft, aber an einer neu­en Ver­si­on wird gearbeitet.