Gibt es Probleme, die einfach zu berechnen, aber schwer zu überprüfen sind?

Vorausgesetzt, P NP, NP-vollständige Probleme sind "schwer zu lösen, haben aber leicht zu überprüfende Antworten." Ist es sinnvoll, das Gegenteil in Betracht zu ziehen, dh Probleme, für die es einfach ist, eine korrekte Antwort zu berechnen, aber eine willkürlich behauptete Lösung nur schwer zu überprüfen? $\neq$

Ich denke, ein solches Problem würde entweder bedeuten:

Exponentiell viele "richtige" Antworten für eine bestimmte Eingabe, da ansonsten die Überprüfung durch einfaches Berechnen aller richtigen Antworten durchgeführt werden könnte.
Einige "richtige" Antworten sind einfach zu berechnen, andere jedoch schwer zu finden.

complexity-theory rphv
quelle

Ich bezweifle das. Wenn eine Antwort einfach zu berechnen ist, ist die Auswahl des Zertifikats einfach: Geben Sie das Problem an, und "überprüfen" Sie die Antwort, indem Sie das Problem lösen, und prüfen Sie, ob es sich bei der angegebenen Antwort tatsächlich um die Antwort handelt.

Patrick87

@ Patrick87 - Ich denke, ich habe das in der Frage angesprochen. Was ist mit einer mehrwertigen Funktion

, die einer Eingabe

eine Menge von Werten

zuordnet ? Nehmen wir an, dass

, und dass es einfach ist, ein Element aus

auszuwählen , aber wenn

es schwierig zu bestimmen, ob

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

rphv

@ Patrick87 Der Löser kann deterministisch sein und nur eine der vorhandenen Antworten ausgeben . Sie müssen dann auf effiziente Weise prüfen, ob zwei Lösungen gleichwertig sind. Kann Äquivalenz an einem Set schwieriger sein, als ein Problem damit zu lösen?

Raphael

Tatsächlich habe ich diesen Teil verpasst, sorry. Trotzdem bin ich geneigt, die Prämisse anzuzweifeln. Ich werde ein bisschen mehr darüber nachdenken und zurückkommen, wenn ich sachdienlichere Gedanken habe.

Patrick87

Ein Zertifikat bedeutet normalerweise, dass es eine einfache Möglichkeit gibt, einen Beweis zu rekonstruieren. Wenn Sie also ein Zertifikat bereitstellen, ist die Überprüfung per Definition einfach. Eine Lösung ohne Zertifikat könnte schwierig sein.

Gilles 'SO- hör auf böse zu sein'

Antworten:

Wenn Sie mit künstlichen Problemen zurechtkommen, können Sie eine Menge davon machen. Hier sind ein paar:

Beantworten Sie bei einer positiven Ganzzahl n in unary eine erfüllbare 3CNF-Formel in n Booleschen Variablen.
Es ist einfach, eine befriedigende 3CNF-Formel zu erhalten, aber zu entscheiden, ob eine bestimmte 3CNF-Formel befriedigend ist oder nicht, ist 3SAT, ein bekanntes NP-vollständiges Problem.
Es erfolgt keine Eingabe. Beantworten Sie einfach eine Turing-Maschine, die anhält (wenn Sie mit einem leeren Eingabeband laufen).
Es ist einfach, eine solche Turingmaschine zu geben, aber ob eine gegebene Turingmaschine anhält oder nicht, ist nicht zu entscheiden.

Hinzugefügt : Ich glaube übrigens nicht, dass das, was Sie im letzten Absatz geschrieben haben, gilt:

Ich denke, ein solches Problem würde exponentiell viele "richtige" Antworten für eine bestimmte Eingabe implizieren, da andernfalls die Überprüfung durchgeführt werden könnte, indem einfach alle richtigen Antworten berechnet werden.

Wenn das Problem eine Lösung hat, ist es nicht schwieriger, eine Antwort zu überprüfen, als die richtige Lösung zu berechnen. Wenn das Problem jedoch eine einfache und eine schwierige Lösung hat, können Sie nicht alle Lösungen effizient berechnen. Hier ist ein solches Problem (das sehr künstlich ist):

Beantworten Sie bei einem Turing-Automaten M eine der folgenden zutreffenden Aussagen: „ M hält auf leerem Eingabeband an“, „ M hält nicht auf leerem Eingabeband an“ und „ M ist ein Turing-Automaten“.
Eine Lösung anzugeben ist einfach : Sie können immer " M ist eine Turing-Maschine" wählen . Ob eine gegebene Antwort jedoch richtig ist oder nicht, ist nicht zu entscheiden. Beachten Sie, dass es in diesem Problem nur zwei Lösungen für jede Instanz gibt.

Tsuyoshi Ito
quelle

Gibt es eine vernünftige Möglichkeit, formal zu definieren, was es bedeutet, wenn solche Probleme „künstlich“ sind? (Mit „vernünftig“, meine ich etwas , das wir auf weit einigen können, wie wenn man sagt , dass eine Definition von „berechenbar“ fängt unsere Intuition , was es bedeuten sollte.)

Gilles ‚SO- Anschlag, der

@ Gilles: Nein, das glaube ich nicht. Ich habe diese Probleme als „künstlich“ bezeichnet, weil es sehr unwahrscheinlich ist, dass jemand zuerst auf diese Probleme stößt und dann herausfindet, dass es einfach ist, eine Antwort zu geben, und es schwierig ist, die Richtigkeit eines bestimmten Antwortkandidaten zu entscheiden. Aber diese „Künstlichkeit“ ist keineswegs ein strenger Begriff.

Tsuyoshi Ito

@ Tsuyoshi Ito - Vielen Dank für Ihre klare Antwort. Ich habe den letzten Absatz bearbeitet, um Ihre Erkenntnisse wiederzugeben.

rphv

Obwohl Tsuyoshi Itos Antwort die "Haupt" -Antwort abdeckt, gab es zwei subtilere Anmerkungen, die ich hinzufügen wollte.

Selbst wenn die Lösung schwer zu überprüfen ist, ist die Überprüfung der Lösung mit einer kurzen Prüfzeichenfolge problemlos möglich. Das heißt, indem die Lösung ein wenig mit zusätzlichen Informationen erweitert wird, kann sie leicht überprüft werden. Die Überprüfung erfolgt immer in NP. Eine Möglichkeit, dies zu erkennen, besteht darin, dass der Agent, der eine Lösung berechnet, alle von ihm verwendeten Zufallsbits aufzeichnen kann. Anschließend kann der Prüfer dieselbe Zufallszeichenfolge verwenden, um dieselbe Berechnung auszuführen. (Der Prüfer muss Zufallsbits verwenden, andernfalls geben sie immer die gleiche Antwort aus, und der Prüfer kann dies jederzeit leicht überprüfen, indem er eine Antwort nach der gleichen Methode berechnet.)
Für Quantencomputer ist dies eine sehr offene Frage. Bei klassischen Computern kann der Prüfer immer so etwas wie den Prüfer simulieren und prüfen, ob er die gleiche Antwort erhält. Es ist durchaus möglich, dass es für ein heikles Problem einen Quantenalgorithmus gibt, der eine gleichmäßige Verteilung über alle (exponentiell vielen) Lösungen erzeugt, die schwer zu überprüfen sind. Sie können den Prüfer nicht erneut ausführen, da Sie höchstwahrscheinlich jedes Mal eine andere Antwort erhalten.

Ein Beispiel für ein ähnliches Problem ist das Deutsch-Jozsa-Problem. Wenn ein Orakel keine ausgewogene Funktion ist, kann ein Quantencomputer schnell feststellen, ob dies der Fall ist, aber es gibt keinen kurzen Beweis, der es einem klassischen Computer ermöglichen würde, dies zu überprüfen. (Dies ist nur ein "ähnliches" Problem, da es immer noch von einem anderen Quantencomputer überprüft werden kann und die Überprüfung auch in klassischem BPP erfolgt, selbst wenn es nicht in P. ist.)

Alex Meiburg
quelle