PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : P und NP


GloomY
2004-04-08, 17:38:12
Kann mir jemand bei meiner Vorbereitung für Informatik III etwas weiterhelfen oder zumindest ein paar hilfreiche Links geben?

Die Klasse P ist (mir) klar, das sind alle Problem, die einen Algorithmus besitzen, der abhängig von der Eingabelänge in polynominialer Zeit das Problem auf einer deterministischen Turingmaschine lösen/berechnen kann.

Bei NP bin ich mir aber nicht so ganz sicher. Eine nichtdeterministische Turingmachine kann ja höchsten sagen: Ja, mit dieser Eingabe kann man in einen akzeptierenden Endzustand gelangen oder eben Nein, diese Eingabe wird nicht akzeptiert (z.B. hält in einem Nicht-Endzustand oder hält gar nicht).

Habe ich das richtig verstanden, dass man also mit einer nichtdet. TM nur prüfen kann, ob eine Eingabe eine Lösung für das Problem ist?
Ist NP dann die Menge aller Probleme, bei denen man in polynominialer Zeit mit einer nichtdet. TM verifizieren kann, ob die Eingabe eine Lösung des Problems ist (also ob die TM akzeptiert)?

Was ist mit der Eingabelänge bei NP? Ist diese bei NP nicht relevant (im Gegensatz zu P)?

Falls irgend was von meinen obigen Ausführungen nicht (ganz) stimmen sollte, bitte ich dringlichst um Korrektur. Bis nächste Woche muss das sitzen :)

Danke für die Mühe =)

Xmas
2004-04-08, 17:51:16
http://de.wikipedia.org/wiki/Komplexit%E4tsklasse_NP
Die englische Version ist informativer.

GloomY
2004-04-08, 18:01:45
Original geschrieben von Xmas
http://de.wikipedia.org/wiki/Komplexit%E4tsklasse_NP
Die englische Version ist informativer. Danke :) Ich glaube aber, die Seite zu kennen.
Original geschrieben von GloomY
oder hält gar nicht).Ist natürlich Blödsinn. Man bekommt ja keine Information über das Akzeptanzverhalten, wenn die TM nicht hält :bonk:

Ausserdem habe ich gerade gelesen, dass NP eine Teilmenge der entscheidbaren Sprachen ist, daher muss die TM immer halten.

mirp
2004-04-08, 20:09:16
Original geschrieben von GloomY
Habe ich das richtig verstanden, dass man also mit einer nichtdet. TM nur prüfen kann, ob eine Eingabe eine Lösung für das Problem ist?
Ja.

Original geschrieben von GloomY
Ist NP dann die Menge aller Probleme, bei denen man in polynominialer Zeit mit einer nichtdet. TM verifizieren kann, ob die Eingabe eine Lösung des Problems ist (also ob die TM akzeptiert)?
Ja. Allerdings enthält NP nicht nur Entscheidungsprobleme, sondern auch Optimierungsprobleme. Wahrscheinlich kann man diese in Entscheidungsprobleme überführen, so dass eine NTM ausreicht.

Original geschrieben von GloomY
Was ist mit der Eingabelänge bei NP? Ist diese bei NP nicht relevant (im Gegensatz zu P)?
Doch, bei NP-Problemen ist die Berechnungszeit der NTM polynomiell beschränkt. Zunächst werden nichtdeterministisch alle möglichen Berechnungswege erraten. Jeder dieser Pfade liegt in P.

GloomY
2004-04-08, 23:14:50
Vielen Dank, mirp. Ich glaube, jetzt ist es mir klar =)

Magnum
2004-04-08, 23:53:38
Original geschrieben von GloomY
Kann mir jemand bei meiner Vorbereitung für Informatik III etwas weiterhelfen oder zumindest ein paar hilfreiche Links geben?
Klar kann ich dir dabei helfen, werde (wurde) dafür ja bezahlt! :)
Original geschrieben von GloomY
Die Klasse P ist (mir) klar, das sind alle Problem, die einen Algorithmus besitzen, der abhängig von der Eingabelänge in polynominialer Zeit das Problem auf einer deterministischen Turingmaschine lösen/berechnen kann.

In P liegen alle Probleme, die sich mit einem determistischen Algrorithmus in polynomieller Zeit lösen lassen. Das hat mit Turingmaschienen erstmal nichts zu tun!
Original geschrieben von GloomY
Bei NP bin ich mir aber nicht so ganz sicher. Eine nichtdeterministische Turingmachine kann ja höchsten sagen: Ja, mit dieser Eingabe kann man in einen akzeptierenden Endzustand gelangen oder eben Nein, diese Eingabe wird nicht akzeptiert (z.B. hält in einem Nicht-Endzustand oder hält gar nicht).
Du verwechselst hier etwas! In NP liegen alle Probleme, die sich nicht-deterministisch in polynomieller Zeit lösen lassen! (Definition) "Man lässt sich vom Orakel ne Lösung geben und kann die in polynomialer Zeit überprüfen lassen!"
Eine nichtdeterministische Turingmaschine hat damit gar nichts zu tun. Nichtdeterministisch heisst hierbei nur, dass es zu einem Zustand mehrere mögliche Übergänge gibt. Bei der DTM gibt es zu jedem Zustand nur einen! Im übringen sind DTM und NTM äquivalent!
Original geschrieben von GloomY
Habe ich das richtig verstanden, dass man also mit einer nichtdet. TM nur prüfen kann, ob eine Eingabe eine Lösung für das Problem ist?
Nein, man kann mit einer NTM alles machen, was man mit einer DTM auch kann!
Original geschrieben von GloomY
Ist NP dann die Menge aller Probleme, bei denen man in polynominialer Zeit mit einer nichtdet. TM verifizieren kann, ob die Eingabe eine Lösung des Problems ist (also ob die TM akzeptiert)?
NP ist die Klasse aller Probleme, die sich nicht-deterministisch in polynomieller Zeit lösen lassen!
Original geschrieben von GloomY
Was ist mit der Eingabelänge bei NP? Ist diese bei NP nicht relevant (im Gegensatz zu P)?
Natürlich ist die Eingabelänge auch bei NP relevant! Du brauchst ja was zu dem dein Algorithmus polynomiell / exponentiell sein soll!
Original geschrieben von GloomY
Falls irgend was von meinen obigen Ausführungen nicht (ganz) stimmen sollte, bitte ich dringlichst um Korrektur. Bis nächste Woche muss das sitzen :)

Danke für die Mühe =)
Keine Ursache, frag ruhig!

Magnum
2004-04-09, 00:01:10
Original geschrieben von mirp
Ja.
Falsch, siehe oben!
Original geschrieben von mirp
Ja. Allerdings enthält NP nicht nur Entscheidungsprobleme, sondern auch Optimierungsprobleme. Wahrscheinlich kann man diese in Entscheidungsprobleme überführen, so dass eine NTM ausreicht.
NTM, siehe oben! Aber Entscheidungsproblem oder Optimierungsproblem spielt keine Rolle! Sie lassen sich meistens eh ineinander überführen, so dass sie letztendlich "äquivalent" sind!
Original geschrieben von mirp
Doch, bei NP-Problemen ist die Berechnungszeit der NTM polynomiell beschränkt. Zunächst werden nichtdeterministisch alle möglichen Berechnungswege erraten. Jeder dieser Pfade liegt in P.
ähh...., Was meinst du mit "werden ndm alle möglichen Berechnungswege erraten"? Der Trick bei NP liegt ja gerade darin, dass nur eine "richtige" Lösung geraten wird, die man dann in polynomieller Zeit berechnen kann!

GloomY
2004-04-09, 00:55:56
Wunderbar, jetzt bin ich wieder verunsichert :| Original geschrieben von Magnum
In P liegen alle Probleme, die sich mit einem determistischen Algrorithmus in polynomieller Zeit lösen lassen. Das hat mit Turingmaschienen erstmal nichts zu tun!Und wie soll man dann den Aufwand messen? Man muss doch festlegen, was eine elementare Operation sein soll, damit man davon reden kann ob oder ob nicht ein Problem mit höchstens polynominialem Aufwand gelöst werden kann.
Original geschrieben von Magnum
Du verwechselst hier etwas! In NP liegen alle Probleme, die sich nicht-deterministisch in polynomieller Zeit lösen lassen! (Definition) "Man lässt sich vom Orakel ne Lösung geben und kann die in polynomialer Zeit überprüfen lassen!"
Eine nichtdeterministische Turingmaschine hat damit gar nichts zu tun.Schön, und womit überprüfst du, wenn nicht mit einer TM?
Original geschrieben von Magnum
Nichtdeterministisch heisst hierbei nur, dass es zu einem Zustand mehrere mögliche Übergänge gibt. Bei der DTM gibt es zu jedem Zustand nur einen!Jep. Ist klar.
Original geschrieben von Magnum
Im übringen sind DTM und NTM äquivalent!Sie sind nur äquivalent bezüglich des Akzeptanzverhaltens. Man kann den Berechnungsbaum einer NTM von einer DTM nach akzeptierenden Endzuständen absuchen lassen und somit eine NTM durch eine DTM simulieren. Beim Aufwandt sieht es jedoch anders aus. (s.u.)
Original geschrieben von Magnum
Nein, man kann mit einer NTM alles machen, was man mit einer DTM auch kann!Manchen ja, aber der Aufwandt ist eben viel größer. Beide TMs haben bezüglich Akzeptanz das gleiche Verhalten, aber wenn es darum geht eine Lösung mit einer NTM zu berechnen, dann dauert das viel länger als mit einer DTM. Bei einer NTM muss man ja alle möglichen Berechnungswege überprüfen, während man bei einer DTM nur den einen Berechnungsweg gehen muss.

*Gähn* , schon viel zu spät. :zzz: Morgen hab' ich mich zum Lernen mit einem Kumpel verabredet. Mit dem werde ich das auch nochmal diskutieren. Bis dann =)

edit: Ich seh' schon, zu NP-Vollständigkeit komme ich dann wohl nicht mehr...

mirp
2004-04-09, 06:59:16
Original geschrieben von Magnum

Falsch, siehe oben!

NTM, siehe oben! Aber Entscheidungsproblem oder Optimierungsproblem spielt keine Rolle! Sie lassen sich meistens eh ineinander überführen, so dass sie letztendlich "äquivalent" sind!

ähh...., Was meinst du mit "werden ndm alle möglichen Berechnungswege erraten"? Der Trick bei NP liegt ja gerade darin, dass nur eine "richtige" Lösung geraten wird, die man dann in polynomieller Zeit berechnen kann! Da bin ich wohl von einem Akzeptor ausgegangen. Sorry.

Beschrieben habe ich die Arbeitsweise, wenn man eine NTM implementieren müsste. Für theoretische Überlegungen reicht es ja zu wissen, wie sich eine NTM nach außen darstellt.

Meine Beschreibung benötigt auch nur polynomiell Zeit zur Berechnung. Jeder Pfad des Berechnungsbaums wird von einer eigenen DTM in polynomieller Zeit parallel abgearbeitet.

mirp
2004-04-09, 07:16:19
Original geschrieben von GloomY

Manchen ja, aber der Aufwandt ist eben viel größer. Beide TMs haben bezüglich Akzeptanz das gleiche Verhalten, aber wenn es darum geht eine Lösung mit einer NTM zu berechnen, dann dauert das viel länger als mit einer DTM. Bei einer NTM muss man ja alle möglichen Berechnungswege überprüfen, während man bei einer DTM nur den einen Berechnungsweg gehen muss.
Eine NTM rechnet nicht länger als eine DTM.

Allerdings lässt sich eine richtige NTM wohl praktisch nicht implementieren, weil man für jeden Pfad des Berechnungsbaumes eine eigene DTM benötigt. Einen solch riesigen Parallel-Rechner wird es in der Praxis nie geben.

Wenn man eine NTM durch eine einzige DTM emuliert, dauert es länger. Das geht dann nicht mehr in polynomieller Zeit.

Magnum
2004-04-09, 10:51:23
Original geschrieben von GloomY
Wunderbar, jetzt bin ich wieder verunsichert :|
Sorry, war keine Absicht!
Original geschrieben von GloomY
Und wie soll man dann den Aufwand messen? Man muss doch festlegen, was eine elementare Operation sein soll, damit man davon reden kann ob oder ob nicht ein Problem mit höchstens polynominialem Aufwand gelöst werden kann.
Für den Aufwand ist nur der Algorithmus (in Pseudocode, o.ä.) entscheidend. Elementare operationen gehen dabei meistens in O(1) und wenn es darum geht, große Zahlen zu behandeln (siehe Primzahlalgorithmus), maximal in O(n).
Original geschrieben von GloomY
Schön, und womit überprüfst du, wenn nicht mit einer TM?
Eine NTM hat mit der Klasse NP nichts zu tun. Also wenn ich nen Algo auf ner NTM habe, heisst das noch lange nicht, dass er in NP liegt!
Dass ich mein geratenes Ergebnis durch ne Turingmaschine überprüfen lasse, ist hierbei normal, muss aber nicht sein. Es würde auch jede andere Rechenmaschine tun, die genauso mächtig, wie ne TM ist! (Im Notfall könntest es selbst du mit Papier un Bleistift tun!)
Original geschrieben von GloomY
Jep. Ist klar.
Original geschrieben von GloomY
Sie sind nur äquivalent bezüglich des Akzeptanzverhaltens. Man kann den Berechnungsbaum einer NTM von einer DTM nach akzeptierenden Endzuständen absuchen lassen und somit eine NTM durch eine DTM simulieren. Beim Aufwandt sieht es jedoch anders aus. (s.u.)
DTM und NTM sind in der Hinsicht äquivalent, in der beide Sprachen vom Typ CH0 akzeptieren.
Dass der Aufwand nicht gleich ist, sieht man ja sofort am Beispiel eines NP-vollständigen Problems. Läuft auf einer NTM in poly. Zeit und auf einer DTM in exponentieller!
Original geschrieben von GloomY
Manchen ja, aber der Aufwandt ist eben viel größer. Beide TMs haben bezüglich Akzeptanz das gleiche Verhalten, aber wenn es darum geht eine Lösung mit einer NTM zu berechnen, dann dauert das viel länger als mit einer DTM. Bei einer DTM muss man ja alle möglichen Berechnungswege überprüfen, während man bei einer NTM nur den einen Berechnungsweg gehen muss.

Du hast hier NTM und DTM verwechselt!
Die DTM muss alle Wege überprüfen, da sie ja nicht weiss, welcher der richitge ist! Die NTM weiss das und braucht dadurch nur einen zu Überprüfen!

GloomY
2004-04-09, 16:53:29
Ich bin grad' ziemlich müde vom lernen, daher erstmal nur eine Antwort auf einen Teil deines Postings, der Rest folgt später :)Original geschrieben von Magnum
Für den Aufwand ist nur der Algorithmus (in Pseudocode, o.ä.) entscheidend. Elementare operationen gehen dabei meistens in O(1) und wenn es darum geht, große Zahlen zu
behandeln (siehe Primzahlalgorithmus), maximal in O(n).Du hast immer noch nicht gesagt, was jetzt konkret eine elementare Operation ist. Und darum geht's ja, dass man eine TM braucht um sagen zu können: Ein Schritt auf der TM ist eine elementare Operation (siehe die Def. unten).
Original geschrieben von Magnum
Eine NTM hat mit der Klasse NP nichts zu tun. Also wenn ich nen Algo auf ner NTM habe, heisst das noch lange nicht, dass er in NP liegt!'Tschuldigung, aber hier liegst du imho völlig falsch.

Ich zitiere mal aus einem Buch (Schöning: Theoretische Informatik - kurzgefasst):
Def.: Für eine nichtdeterministsche Turingmaschine M sei ntime(x) = { 0 , falls x nicht Element T(M)

min( Länge einer akzeptierenden Rechnung
von M auf x) , falls x Element T(M)
}Sei f: N -> N eine Funktion. Die Klasse NTIME( f(n) ) besteht aus allen Sprachen A, für die es eine nichtdeterministische Mehrband-Turingmaschine M gibt mit A = T(M) und ntime(x) <= f(|x|).

Ferner definieren wir:

NP := Vereinigung ( NTIME(p(n)) unter allen Polynomen pGemeint ist dieses komische "U" mit "p Polynom" drunterstehend.

Es sollte klar sein, dass NP sehr wohl etwas mit einer nichtdeterministischen TM zu tun hat.
Original geschrieben von Magnum
Dass der Aufwand nicht gleich ist, sieht man ja sofort am Beispiel eines NP-vollständigen Problems. Läuft auf einer NTM in poly. Zeit und auf einer DTM in exponentieller!Wenn du davon ausgehst, dass P != NP ist, dann gibt es für die NP-vollständigen Probleme keinen polynominialen Algorithmus, ergo mindestens exponentiell. Dass P != NP gilt, ist zwar wahrscheinlich, aber bisher nicht bewiesen.

Magnum
2004-04-09, 17:42:50
Original geschrieben von GloomY
Ich bin grad' ziemlich müde vom lernen, daher erstmal nur eine Antwort auf einen Teil deines Postings, der Rest folgt später :)Du hast immer noch nicht gesagt, was jetzt konkret eine elementare Operation ist. Und darum geht's ja, dass man eine TM braucht um sagen zu können: Ein Schritt auf der TM ist eine elementare Operation (siehe die Def. unten).
Meistens sind Elemetare Operationen sowas wie +, -, *, /, Vergleiche und was sich sonst noch schnell berechnen lässt. Genauer kann ich es auch nicht sagen, da es in der Tat, wie du schon sagtest, davon abhängt, welche Rechenarchitektur ich zugrunde lege!
Zum Beispiel: Der Algorithmus, der ein Wort auf Palindrom überprüft, hat auf einer normalen DTM eine Laufzeit von O(n^2). Nimmt man jetzt aber eine zweikopf TM oder eine TM mit zwei Bändern hat der Algo plötzlich ne Laufzeit von O(n).
Verstehst du? Alles was ich damit sagen wollte, war, dass es nicht auf die Turingmaschine ankommt, ob ein Algorithmus in P liegt oder nicht! (Hauptsache er lässt sich irgendwie polynomiell implementieren!)
Original geschrieben von GloomY
'Tschuldigung, aber hier liegst du imho völlig falsch.

Ich zitiere mal aus einem Buch (Schöning: Theoretische Informatik - kurzgefasst):
Gemeint ist dieses komische "U" mit "p Polynom" drunterstehend.

Es sollte klar sein, dass NP sehr wohl etwas mit einer nichtdeterministischen TM zu tun hat.
OK, schau dir mal folgende Definition an (nach Prof. D.Wagner): "Die Klasse NP ist die Menge aller Sprachen L, für die es eine NTM gibt, deren Zeitkomplexitätsfunktion polynomial beschränkt ist!"
Also allein schon durch die Definition haben sie was miteinander zu tun!
Aber bevor du jetzt denkst, dass ich falsch lag, überleg mal, was ich gesagt habe! Brauche ich wirklich eine NTM um eine Problemlösung zu überprüfen? Kann ich nicht auch hingehen, mir eine Lösung raten und diese von einer anderen Maschine (es gibt andere Modell, RAM z.B.) überprüfen lassen! Ich brauche also nicht unbedingt eine NTM!!

Von was ich dich eigentlich abhalten wollte, dass bei dir der Gedanke aufkommt, alles was auf einer NTM läuft gleich mit NP zu assozieren! Das Problem QBF-SAT kann ich nämlich auch auf einer NTM lösen lassen, nur liegt es nicht in NP!

Original geschrieben von GloomY
Wenn du davon ausgehst, dass P != NP ist, dann gibt es für die NP-vollständigen Probleme keinen polynominialen Algorithmus, ergo mindestens exponentiell. Dass P != NP gilt, ist zwar wahrscheinlich, aber bisher nicht bewiesen.
Solange P=NP niemand bewiesen hat, gehe ich davon aus, dass P != NP gilt! (hatte ich vergessen zu sagen, Sorry!)

GloomY @ Uni
2004-04-10, 11:04:12
Original geschrieben von Magnum
Meistens sind Elemetare Operationen sowas wie +, -, *, /, Vergleiche und was sich sonst noch schnell berechnen lässt. Genauer kann ich es auch nicht sagen, da es in der Tat, wie du schon sagtest, davon abhängt, welche Rechenarchitektur ich zugrunde lege!
Zum Beispiel: Der Algorithmus, der ein Wort auf Palindrom überprüft, hat auf einer normalen DTM eine Laufzeit von O(n^2). Nimmt man jetzt aber eine zweikopf TM oder eine TM mit zwei Bändern hat der Algo plötzlich ne Laufzeit von O(n).
Verstehst du? Alles was ich damit sagen wollte, war, dass es nicht auf die Turingmaschine ankommt, ob ein Algorithmus in P liegt oder nicht! (Hauptsache er lässt sich irgendwie polynomiell implementieren!)Gibt es nicht aber Probleme, die auf der einen Maschine polynomiale Laufzeit haben und auf einer anderen (langsamen) exponentiellen Aufwand? Muss man nicht deshalb darüber einigen, welche Maschine man heranzieht um festzulegen, was eine elementare Operation ist?
Original geschrieben von Magnum
OK, schau dir mal folgende Definition an (nach Prof. D.Wagner): "Die Klasse NP ist die Menge aller Sprachen L, für die es eine NTM gibt, deren Zeitkomplexitätsfunktion polynomial beschränkt ist!"
Also allein schon durch die Definition haben sie was miteinander zu tun!
Aber bevor du jetzt denkst, dass ich falsch lag, überleg mal, was ich gesagt habe! Brauche ich wirklich eine NTM um eine Problemlösung zu überprüfen? Kann ich nicht auch hingehen, mir eine Lösung raten und diese von einer anderen Maschine (es gibt andere Modell, RAM z.B.) überprüfen lassen! Ich brauche also nicht unbedingt eine NTM!!

Von was ich dich eigentlich abhalten wollte, dass bei dir der Gedanke aufkommt, alles was auf einer NTM läuft gleich mit NP zu assozieren! Das Problem QBF-SAT kann ich nämlich auch auf einer NTM lösen lassen, nur liegt es nicht in NP!Ich kenne zwar QBF-SAT nicht, aber liege ich mit der Annahme richtig, dass wenn das Problem auf einer NTM lösbar ist, aber nicht in NP liegt, dass QBF-SAT dann nicht polynomial beschränkt ist? (Weil sonst wäre es doch in NP?!)

Ist die Zugehörigkeit zu NP also an zwei Bedingungen geknüpft? (Lösbarkeit auf einer NTM und dabei maximal polinomialer Aufwand)

Ansonsten wäre ich sehr verunsichert... :|

GloomY @ Uni
2004-04-10, 11:43:58
Ok, ich hab'mir grad' QBF-SAT angeschaut. Imho hat es exponentiellen Aufwand, weil für jeden Allquantor die quantifizierte Formel für alle Belegungen wahr sein muss. Bei n Allquantoren muss man also 2 hoch n verschiedene Belegungen der Variablen anschauen, um festzustellen, ob die Formel wahr ist.

Im schlimmsten Fall (also wenn alle Qantoren Allquantoren sind) hat man also eponentiellen Aufwand bezüglich der Eingabelänge (Anzahl der Variablen in der Formel = Anzahl der Quantoren).

Magnum
2004-04-10, 12:20:26
Original geschrieben von GloomY @ Uni
Gibt es nicht aber Probleme, die auf der einen Maschine polynomiale Laufzeit haben und auf einer anderen (langsamen) exponentiellen Aufwand? Muss man nicht deshalb darüber einigen, welche Maschine man heranzieht um festzulegen, was eine elementare Operation ist?
Solche Probleme sind mir nicht bekannt! Aber ich geb dir jetzt nen gut gemeinten Rat: Halte dich nicht solange mit Frage auf welche Laufzeit dein Algorithmus auf welcher Maschine hat.
Setze halt einfach ne normale TM voraus. Wenn sie das in der Klausur nicht vorgeben, können sie es dir nicht als Fehler ankreiden! (Und außerdem gibt es wichtigere Dinge in dieser Klausur als O-Kalkül)
Original geschrieben von GloomY @ Uni
Ist die Zugehörigkeit zu NP also an zwei Bedingungen geknüpft? (Lösbarkeit auf einer NTM und dabei maximal polinomialer Aufwand)

Im Prinzip stimmts! Nur musst du mit dem Wort Lösbarkeit aufpassen. Gemeint ist ja nur die Überprüfung einer möglichen Lösung auf Korrektheit, die in polynoialer Zeit geschehen muss!

Magnum
2004-04-10, 12:21:00
Original geschrieben von GloomY @ Uni
Ok, ich hab'mir grad' QBF-SAT angeschaut. Imho hat es exponentiellen Aufwand, weil für jeden Allquantor die quantifizierte Formel für alle Belegungen wahr sein muss. Bei n Allquantoren muss man also 2 hoch n verschiedene Belegungen der Variablen anschauen, um festzustellen, ob die Formel wahr ist.

Im schlimmsten Fall (also wenn alle Qantoren Allquantoren sind) hat man also eponentiellen Aufwand bezüglich der Eingabelänge (Anzahl der Variablen in der Formel = Anzahl der Quantoren).
Richtig! :)
Im schlimmsten Fall dauert hier allein die Überprüfung einer möglichen Lösung exponentielle Zeit! Deswegen ist QBF-SAT nicht mehr in NP!

Gast
2004-04-10, 12:52:48
Original geschrieben von Magnum
Solche Probleme sind mir nicht bekannt! Aber ich geb dir jetzt nen gut gemeinten Rat: Halte dich nicht solange mit Frage auf welche Laufzeit dein Algorithmus auf welcher Maschine hat.
Setze halt einfach ne normale TM voraus. Wenn sie das in der Klausur nicht vorgeben, können sie es dir nicht als Fehler ankreiden! (Und außerdem gibt es wichtigere Dinge in dieser Klausur als O-Kalkül)Ja, das mit der TM vorraussetzen hab' ich doch gesagt. ;)
Original geschrieben von Magnum
Im Prinzip stimmts! Nur musst du mit dem Wort Lösbarkeit aufpassen. Gemeint ist ja nur die Überprüfung einer möglichen Lösung auf Korrektheit, die in polynoialer Zeit geschehen muss! Das "lösen" kam eigentlich von dir: ;)Original geschrieben von Magnum
Das Problem QBF-SAT kann ich nämlich auch auf einer NTM lösen lassen, nur liegt es nicht in NP!

Aber nochmal zu der Frage, was eine NTM macht. Man kann also eigentlich nur eine Lösung verifizieren (nachdem man eine geraten hat), richtig?

Eine DTM kann ja wirklich rechen (= Realisierung einer Funktion f: Eingabe auf Band vor Start der DTM -> Ausgabe auf Band nach Ablauf der DTM), also z.B. f(x)=x+1 (dafür kann ich sogar eine DTM angeben ;) ).

Die Abarbeitung einer NTM ist ja nicht deterministisch, d.h., dass bei jedem neuen Ablauf kann etwas anderes am Ende auf dem Band stehen. Man kann also mit einer NTM nicht wirklich Rechnen, aber dafür verifizieren (wenn man die richtige Abfolge der Konfigurationen vorraus-orakelt), richtig?

edit: Ach ja, ich bin's ;)

Magnum
2004-04-10, 13:56:57
Original geschrieben von Gast
Ja, das mit der TM vorraussetzen hab' ich doch gesagt. ;)
Das "lösen" kam eigentlich von dir: ;)
OOPS! :)
Original geschrieben von Gast
Aber nochmal zu der Frage, was eine NTM macht. Man kann also eigentlich nur eine Lösung verifizieren (nachdem man eine geraten hat), richtig?

Eine DTM kann ja wirklich rechen (= Realisierung einer Funktion f: Eingabe auf Band vor Start der DTM -> Ausgabe auf Band nach Ablauf der DTM), also z.B. f(x)=x+1 (dafür kann ich sogar eine DTM angeben ;) ).

Die Abarbeitung einer NTM ist ja nicht deterministisch, d.h., dass bei jedem neuen Ablauf kann etwas anderes am Ende auf dem Band stehen. Man kann also mit einer NTM nicht wirklich Rechnen, aber dafür verifizieren (wenn man die richtige Abfolge der Konfigurationen vorraus-orakelt), richtig?

edit: Ach ja, ich bin's ;)
Naja, eigentlich kann eine NTM auch rechnen! DTM und NTM sind ja äquivalent!
DU kannst garantiert auch ein Programm für eine NTM angeben, die f(x)=x+1 berechnet! Das liegt ja daran, dass die TM die Funktion berechnet und dann in einen akzeptierenden Zustand wechselt! Bei einer DTM ist alles nachvollziehbar, wie gerechnet wurde (deterministisch eben)! Die NTM hingegen akzeptiert ja, wenn es einen!! möglichen Weg gibt, der zu einer richtigen Lösung führt! (Zu deinem Beispiel, müsstest du nur noch ne Regel hinzufügen, die am Ende 2 addiert! Jetzt ist deine DTM nichtdeterministisch, du kannst ja wählen +1 oder +2, aber es gibt eine richtige Lösung, also akzeptiert sie!)

Eine NTM ist also deswegen so gut zum Verifizieren, da ich nicht genau wissen muss, wie ich auf die Lösung komme! Hauptsache es gibt eine und der Weg dorthin ist polynomial ==> NP!
Die DTM muss alle mögliche Lösungen durchprobieren, was im allgemeinen exp. Laufzeit hat.

GloomY
2004-04-11, 19:58:06
Original geschrieben von Magnum
Naja, eigentlich kann eine NTM auch rechnen! DTM und NTM sind ja äquivalent!
DU kannst garantiert auch ein Programm für eine NTM angeben, die f(x)=x+1 berechnet! Das liegt ja daran, dass die TM die Funktion berechnet und dann in einen akzeptierenden Zustand wechselt! Bei einer DTM ist alles nachvollziehbar, wie gerechnet wurde (deterministisch eben)! Die NTM hingegen akzeptiert ja, wenn es einen!! möglichen Weg gibt, der zu einer richtigen Lösung führt! (Zu deinem Beispiel, müsstest du nur noch ne Regel hinzufügen, die am Ende 2 addiert! Jetzt ist deine DTM nichtdeterministisch, du kannst ja wählen +1 oder +2, aber es gibt eine richtige Lösung, also akzeptiert sie!)Ja, es ist mir schon klar, dass wenn es eine mögliche Lösung für die NTM gibt, diese akzeptiert. Ich störe mich aber nur an der Bezeichnung "Rechnen", weil es ja eigentlich kein Rechnen sondern ein Verifizieren ist. Wenn eine NTM akzeptiert, beantwortet das ja nur die Frage, ob es eine Folge von Konfigurationen mit Akzeptanz gibt. Eine andere Abfolge von Konfigurationen kann bei gleicher Eingabe aber zu einem anderen Ergebnis kommen (und auch akzeptieren).

Das ist eben der Unterschied zwischen der Übergangsfunktion von NTM und DTM. Diese ist bei einem NTM eine Funktion im mathematischen Sinne (eindeutige Zuordnung von Argument zu Funktionswert), während es bei einer NTM ja nur eine Relation ist (d.h. es kann mehrere Nachfolgekonfigurationen geben).
Original geschrieben von Magnum
Eine NTM ist also deswegen so gut zum Verifizieren, da ich nicht genau wissen muss, wie ich auf die Lösung komme! Hauptsache es gibt eine und der Weg dorthin ist polynomial ==> NP!
Die DTM muss alle mögliche Lösungen durchprobieren, was im allgemeinen exp. Laufzeit hat. Hmm ja.

Jetzt hab' ich noch ein paar Fragen zur NP-Vollständigkeit und zu NP-schweren (-harten) Problemen. Also NP-Vollständig sind alle Probleme, die

1.) in NP liegen und
2.) bei denen sich ALLE Probleme aus NP in polynomialer Zeit reduzieren lassen,

Richtig?

(wegen 2. ist man auf der Suche nach einem in polynomialer Zeit deterministisch lösbaren Problem aus NP-V, weil dann P=NP bewiesen wäre; bzw. dem Beweis, dass es keinen solchen gibt und damit dann P!=NP wäre)

NP-schwer sind alle Probleme, bei denen sich ALLE Probleme aus NP in polynomialer Zeit reduzieren lassen.

D.H. NP geschnitten NP-schwer = NP-Vollständig, richtig?

Magnum
2004-04-11, 20:59:06
Original geschrieben von GloomY
Jetzt hab' ich noch ein paar Fragen zur NP-Vollständigkeit und zu NP-schweren (-harten) Problemen. Also NP-Vollständig sind alle Probleme, die

1.) in NP liegen und
2.) bei denen sich ALLE Probleme aus NP in polynomialer Zeit reduzieren lassen,

Richtig?

(wegen 2. ist man auf der Suche nach einem in polynomialer Zeit deterministisch lösbaren Problem aus NP-V, weil dann P=NP bewiesen wäre; bzw. dem Beweis, dass es keinen solchen gibt und damit dann P!=NP wäre)

NP-schwer sind alle Probleme, bei denen sich ALLE Probleme aus NP in polynomialer Zeit reduzieren lassen.

D.H. NP geschnitten NP-schwer = NP-Vollständig, richtig?
Im Prinzip alles richtig!

NP vollständige Probleme erfüllen folgende Eigenschaften:
1. Sie liegen in NP
und 2. Sie sind NP-hart (NP-schwer)
NP-hart bedeutet soviel, dass sich alle Probleme aus NP auf das eine Problem reduzieren lassen! Dies wird i.a. dadurch gezeigt, dass man ein schon bekanntes NP-schweres Problem auf das neue Problem reduziert!

GloomY
2004-04-12, 01:31:44
Ok, dann erstmal schon vielen Dank an Dich, Magnum =)

Ich werde mir dann mal die Unmengen an NP-vollständigen Problemen in meinem Script anschauen ;)