Home

P und NP - Für Laien erklärt

Montag, 9. August 2010 | Autor:

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­schine1 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.

  1. Genauer gesagt einer Turing­ma­schine - aber es ist für die­sen Arti­kel auch okay, wenn man sich ein­fach nur einen PC vor­stellt.

Tags »

Trackback: Trackback-URL |  Feed zum Beitrag: RSS 2.0
Thema: Informatik

Diesen Beitrag kommentieren.

6 Kommentare

  1. 1
    Ella 

    Tolle Erklä­rung! Dankeschön!

  2. 2
    JDR 

    Also ich hab das so ver­stan­den
    … Man ver­sucht zu bewei­sen das ein PC inner­halb von Sekun­den eine Berech­nung durch­füh­ren kann, wofür ein der­zei­ti­ger Com­pu­ter nicht ein­mal in der Lage wäre bzw unend­lich lange für die Berech­nung bräuchte? Ist das in etwa so ahn­lich wie ein nor­ma­ler PC zu einem Quan­ten PC oder wie sich diese Art Com­pu­ter nennt an denen soweit ich weis eben­falls geforscht wird? Ich hab lei­der noch nicht ganz das wis­sen zu ver­ste­hen was mit poly­no­mi­el­ler Lauf­zeit etc gemeint ist…

  3. 3
    Nico 

    Es geht wirk­lich nur darum, wie die For­mel aus­sieht, die beschreibt, wie­viele Ope­ra­tio­nen man bei einer bestimm­ten Pro­blem­größe n braucht. Beim Hän­de­schüt­teln sind es eben eine qua­dra­ti­sche For­mel, also ein Poly­nom vom Grad 2, also ist das Hän­de­schüt­teln ein Pro­blem mit poly­no­mi­el­ler Lauf­zeit.
    Wich­tig ist noch: Ich habe in die­ser Argu­men­ta­tion nicht erwähnt, wie schnell die Hände geschüt­telt wer­den! Der Grund ist, dass es nicht wich­tig ist, denn ange­nom­men ich mache, dass das es dop­pelt so schnell geht: was pas­siert dann mit der For­mel für die Lauf­zeit? Es kommt vorn ein Fak­tor 0.5 dazu, aber daran, dass es ein Poly­nom ist, ändert sich dadurch nichts :)
    Es geht also nicht darum, wie schnell mein Com­pu­ter ist, son­dern eben ob die For­mel ein Poly­nom ist, oder etwas ande­res, was schnel­ler ansteigt Bei­spiels­weise etwas mit exp(n) oder n! (n Fakul­tät) darin.

  4. 4
    :) 

    Hallo?

  5. 5
    :) 

    Ich sitze gerade im Info unter­richt und tue so als würde ich arbeiten.

  6. 6
    Rumpelstielzchen 

    Moin Jungs ich bins ihr euern Rrum­pel­stielz­chen
    Ich habe dat Pro­blem gelöst! Mich meine Jun­gens und ich warnse ges­tern aufn Sport­platz an kicen. Biste nache Schicht ine Trink­halle gegan­gen ums dich ein zu Schüt­ten und dann hamwa den Kack da kurz gelöst
    P ist gleich Np
    Warum?
    Weil ich dat sagen tu!

Kommentar abgeben