Marco D. - Mo 23.03.09 18:45
Titel: Komplexität: Unterschied EXPTime und NP

---

Hallo zusammen,

ich schreibe am Freitag eine Klausur zu den Grundlagen der Informatik.
Kann mir bitte jemand mal den Unterschied zwischen den Komplexitätsklassen EXPTime und NP klarmachen?
Hab schon an mehreren Stellen gesucht und nachgeschlagen, aber die genauen Unterschiede wurden nirgends aufgezeigt.

Gruß
Marco

delfiphan - Mo 23.03.09 22:25

---

NP <= PSPACE <= EXPTIME

NP braucht max. p(n) viel Zeit auf einer nicht-deterministischen Turingmaschine. PSPACE braucht max. p(n) viel Speicher auf einer (deterministischen oder nicht-deterministischen) Turingmaschine und ExpTime braucht max. 2^p(n) viel Zeit auf einer deterministischen Turingmaschine. Ob diese Klassen äquivalent ist, ist nicht bekannt. Man geht davon aus, dass die beide Inklusionen echt sind.

Marco D. - Mo 23.03.09 22:31

---

Mir geht es konkret um die Unterschiede zwischen NP und ExpTime.

ExpTime braucht also exponentiellen Aufwand auf einer deterministischen Turing-Maschine. Und wieviel Aufwand braucht NP auf einer deterministischen Turing-Maschine? In der Wikipedia werden meines Erachtens die Unterschiede nicht deutlich gemacht.
Konkret: Was hat ein Problem aus ExpTime, was die Probleme aus NP nicht haben?

delfiphan - Mo 23.03.09 22:37

---

Marco D. hat folgendes geschrieben :

Und wieviel Aufwand braucht NP auf einer deterministischen Turing-Maschine.

Wenn du das genau rausfindest, bist du Millionär.

Gausi - Mo 23.03.09 22:39

---

NP sind die Probleme, die auf einer Nichtdeterministischen Maschine in Polynomzeit gelöst werden können. Wenn man die Berechnung der NP-Maschine deterministisch simulieren will, geht das in EXPTime

Umgekehrt ist aber nicht unbedingt jedes deterministisch in exponentieller Zeit lösbare Problem auch nichtdeterministisch in polynomieller Zeit lösbar. Zumindest fällt mir dafür kein einfaches Argument ein, und wenn delfiphan Recht hat (davon gehe ich mal aus) bin ich damit nicht alleine. ;-)

Grob gesagt: Das eine sind Äpfel, das andere Birnen. :mrgreen:

delfiphan - Mo 23.03.09 22:47

---

Gausi hat folgendes geschrieben :

Umgekehrt ist aber nicht unbedingt jedes deterministisch in exponentieller Zeit lösbare Problem auch nichtdeterministisch in polynomieller Zeit lösbar

Naja, theoretisch könnte NP = EXPTIME sein. Ausgeschlossen ist es nicht. Vermutlich beinhaltet EXPTIME aber weit mehr als NP.

Gausi - Mo 23.03.09 22:53

---

Da steckt ein "unbedingt" drin, was zum Audruck bringen sollte, dass ich das nicht weiß, womit ich wohl in guter Gesellschaft bin. Deswegen auch der Folgesatz. ;-)

(Das schöne an Prüfungen in Komplexitätstheorie ist, dass die Antwort "Weiß ich nicht" genau richtig sein kann. :D)

delfiphan - Mo 23.03.09 22:57

---

Marco D. hat folgendes geschrieben :

Konkret: Was hat ein Problem aus ExpTime, was die Probleme aus NP nicht haben?

Man weiss es nicht (mit Sicherheit). Vielleicht sind die zwei identisch. Man hat die Definitionen und Beispiele dazu. Die kannst du meinetwegen miteinander Vergleichen. Aber viel mehr kann man eigentlich fast nicht dazu sagen...

Du musst wohl einfach die Definitionen kennen, evtl. einige Beispiele zu den einzelnen Klassen und die Teilmengen.

P <= NP <= PSPACE <= EXPTIME <= NEXPTIME <= EXPSPACE
P < EXPTIME, NP < NEXPTIME, PSPACE < EXPSPACE (kurz, mind. eine der ersten und mind. eine der letzten 3 Teilmengen sind strikt)
Falls P = NP, dann EXPTIME = NEXPTIME

Vermutlich sind es aber alles echte Teilmengen.

Was man halt sieht ist, dass, man NP ganz sicher mit PSPACE oder in EXPTIME lösen kann, d.h. mit p(n) Speicher und 2^p(n) Zeit kannst du sicher ein NP Problem lösen. Es wäre aber möglich, dass P=NP ist, dann würde p(n) Zeit reichen.

Das ist so wie wenn man mal zwei Klassen definiert "Geräte mit einem Prozessor" und "Elektronikgerät". Zuerst hältst du diese für zwei verschiedene Dinge mit gewisser Ähnlichkeit, dann findest du heraus, dass ein Gerät mit einem Prozessor immer ein Elektronikgerät ist. Du fragst jetzt: "Was hat ein Elektronikgerät, was Geräte mit einem Prozessor nicht haben". Naja, ein Elektronikgerät ohne Prozessor müsste es auf jeden Fall sein. Ob's das gibt, weiss ich nicht, aber ich bin mir fast sicher, dass es das geben muss. Und wenn man das bewiesen hat, müsste man noch ein gemeinsames Merkmal finden, um die Frage zu beantworten :|...
Ein ExpSpace Problem, dass nicht in NP ist. Ob's das gibt, weiss man nicht, aber man ist sich fast sicher, dass es das geben muss. Hm...