Home

P und NP - Für Laien erklärt

Montag, 9. August 2010 | Autor:

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 dau­ern.

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 berech­nen?

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­ne1 in poly­no­mi­el­ler Zeit lösen las­sen. Genau­er: Pro­ble­me, die sich in poly­no­mi­ell 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­mi­ell 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­mi­el­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­mi­el­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­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 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 gear­bei­tet.

  1. Genau­er gesagt einer Turing­ma­schi­ne - 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.

8 Kommentare

  1. 1
    Ella 

    Tol­le Erklä­rung! Dan­ke­schö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 lan­ge für die Berech­nung bräuch­te? Ist das in etwa so ahn­lich wie ein nor­ma­ler PC zu einem Quan­ten PC oder wie sich die­se 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 dar­um, wie die For­mel aus­sieht, die beschreibt, wie­vie­le 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­ti­on nicht erwähnt, wie schnell die Hän­de 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 dar­an, dass es ein Poly­nom ist, ändert sich dadurch nichts 🙂
    Es geht also nicht dar­um, 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­wei­se etwas mit exp(n) oder n! (n Fakul­tät) dar­in.

  4. 4
    :) 

    Hal­lo?

  5. 5
    :) 

    Ich sit­ze gera­de im Info unter­richt und tue so als wür­de ich arbei­ten.

  6. 6
    Rumpelstielzchen 

    Moin Jungs ich bins ihr euern Rrum­pel­sti­elz­chen
    Ich habe dat Pro­blem gelöst! Mich mei­ne Jun­gens und ich warn­se ges­tern aufn Sport­platz an kicen. Bis­te nache Schicht ine Trink­hal­le gegan­gen ums dich ein zu Schüt­ten und dann ham­wa den Kack da kurz gelöst
    P ist gleich Np
    War­um?
    Weil ich dat sagen tu!

  7. 7
    Lena 

    Ich füh­le mit dir Bru­der :DDDDDDDDDDDDDDDDDDDDDDDDDDDDD

  8. 8
    alzner michael 

    pro­biert es mal mit:
    N=1 oder P=0
    oder P ist nicht NP
    P=0 oder N=1

Kommentar abgeben