Das ist meine erste Stackoverflow-Frage, also sei sanft. Ich entschuldige mich im Voraus, wenn das schon zu Tode geprügelt wurde ... Ich habe ein paar Threads über NP gelesen, aber ich habe keine verlockende Antwort auf meine Frage gefunden (wenn überhaupt, habe ich ein paar neue gefunden). Kurz gesagt:
Mein Verdacht ist, dass die Antwort auf die erste Frage ein klares "Ja" ist und dass die Antwort auf das zweite ein klares Nein ist.
Im ersten Fall könnte ein Beispielproblem sein "gegeben eine Menge S, eine Teilmenge T von S und eine Funktion f mit Domäne 2 ^ S, bestimmen, ob T maximiert f". Für generische S, T und f, können Sie dies nicht einmal überprüfen, ohne f (X) für alle Teilmengen X von S zu prüfen, oder?
Im zweiten Fall ... nun, ich gebe zu, das ist mehr eine Ahnung. Aus irgendeinem Grund scheint es nicht wichtig zu sein, ob eine Antwort ein Bit (für Entscheidungsprobleme) oder irgendeine (endliche) Anzahl von Bits enthält ... oder mit anderen Worten, warum Sie nicht in der Lage sein sollten, darüber nachzudenken die auf dem Band verbliebenen Symbole, nachdem das TM als Teil der "Antwort" angehalten wurde.
BEARBEITEN: Eigentlich habe ich eine Frage ... wie genau zeigt Ihre Konstruktion, dass Funktionsprobleme "nicht schwieriger" sind als Entscheidungsprobleme? Wenn überhaupt, haben Sie gezeigt, dass es nicht einfacher ist, ein Funktionsproblem als ein Entscheidungsproblem zu beantworten ... was trivial ist. Vielleicht ist das meine Schuld, wenn ich die Frage schlampig gestellt habe.
Gegeben ein TM T1 in NP, das das Problem "Ist X eine Lösung des Problems P" für die Variable X und (der Argumentation halber) fixiertes P, löst, ist garantiert, dass es ein TM T2 in NP geben wird, das anhält überall hält T1 an, was im "Halt akzeptieren" -Zustand endet, wo es auch hält, und verlässt z eine binäre Darstellung von X auf dem Band?
(1) Ja, es gibt Entscheidungsprobleme, die entscheidbar sind, aber nicht in NP. Es ist eine Folge des Zeithierarchiesatz , dass NP ⊊ NEXP , also ist kein NEXP-schwieriges Problem in NP. Das kanonische Beispiel ist dieses Problem:
Wenn eine nicht-deterministische Turing-Maschine M und eine ganze Zahl n binär geschrieben wird, akzeptiert M die leere Zeichenfolge in höchstens < em> n Schritte?
Dieses Problem ist sicherlich entscheidbar (simulieren Sie einfach alle Berechnungspfade für M der Länge n und wenn irgendwelche akzeptiert werden).
Siehe diese Frage auf cstheory.stackexchange.com für viele weitere NEXP -vollständige Probleme. Und natürlich gibt es Entscheidungsprobleme außerhalb von NEXP: in der Tat eine ganze exponentielle Hierarchie von ihnen ...
(2) Die Antwort auf Ihre zweite Frage lautet: Funktionsprobleme sind nicht schwieriger als Entscheidungsprobleme. (In einem speziellen technischen Sinn von "nicht schwieriger als".) Angenommen, wir haben ein Funktionsproblem, das nach Ausgabe N fragt. Dann gibt es ein Entscheidungsproblem, das eine Eingabe k nimmt und fragt, ob das k -te Bit von N <1 ist. Lösen Sie dieses Entscheidungsproblem für jedes Bit in der Antwort, und du bist fertig!
Zum Beispiel kann FSAT (das Problem von das Finden einer befriedigenden Zuweisung zu einer booleschen Formel) sein reduzierte Polynomialzeit zu SAT (das Problem von zu bestimmen, ob eine Boolesche Formel eine befriedigende Zuweisung hat). Angenommen, Sie können SAT lösen, und Sie werden aufgefordert, eine befriedigende Zuweisung für die Formel φ zu finden. Betrachten Sie die erste Variable x in Ihrer Formel φ und fragen Sie SAT, ob x ∧φ erfüllbar ist. Wenn dies der Fall ist, muss es eine erfüllende Zuweisung für φ geben, in der x wahr ist; Wenn nicht, und φ erfüllbar ist, dann muss es eine erfüllende Zuweisung für φ geben, in der x falsch ist. Fahren Sie mit der zweiten Variablen y fort und fragen Sie, ob x ∧ y ∧φ (oder ¬ x ∧ ) ist y ∧φ, nach der Antwort auf Ihre erste Frage) ist erfüllbar. Und so weiter für jede Variable in der Formel.
[Ich sollte eine wichtige Einschränkung zu diesem Beispiel hinzufügen. Hier sind SAT und FSAT "natürlich" verwandt: Beide haben es mit der gleichen Sache zu tun, nämlich die Erfüllung von Formeln. Aber in meinem Argument, dass die Suche im Allgemeinen auf die Entscheidung reduziert werden kann, habe ich ein hochartifizielles Entscheidungsproblem über das k -te Bit der Ausgabe verwendet. Obwohl also die Suche auf eine Entscheidung reduziert wird, reduziert sie sich nicht notwendigerweise auf das natürliche entsprechende Entscheidungsproblem. Insbesondere zeigten Bellare und Goldwasser, dass Suche manchmal nicht so reduziert werden kann.]
Tags und Links complexity-theory np