Gibt es eine Aufgabe, die in der Polynomzeit lösbar, in der Polynomzeit jedoch nicht überprüfbar ist?

Ein Kollege von mir und ich haben gerade einige Notizen von einem unserer Professoren getroffen. Die Notizen besagen, dass es Aufgaben gibt, die in Polynomzeit gelöst werden können (in der Klasse von PF), die jedoch in Polynomzeit NICHT überprüfbar sind (in der Klasse von NPF NICHT).

Um auf diese Klassen einzugehen: Wir erhalten eine Eingabe X und erzeugen eine Ausgabe Y, so dass (X, Y) in Beziehung R stehen und unsere Aufgabe darstellen. Wenn es möglich ist, Y für X in Polynomialzeit zu erhalten, gehört die Aufgabe zur Klasse von PF. Wenn es möglich ist, das Polynomlängenzertifikat Z zu verifizieren, das beweist, dass ein Tupel (X, Y) in Polynomzeit in Relation R ist, gehört die Aufgabe zur Klasse der NPF.

Es handelt sich nicht um Entscheidungsprobleme, bei denen die Antwort einfach JA oder NEIN lautet (eher formal, wenn ein String zu einer Sprache gehört). Bei Entscheidungsproblemen scheint es, dass PF eine richtige Teilmenge von NPF ist. Bei anderen Aufgaben kann dies jedoch anders sein.

Kennen Sie eine Aufgabe, die in Polynomzeit gelöst, in Polynomzeit aber nicht verifiziert werden kann?

complexity-theory np Drozi
quelle

Vielleicht habe ich ein Missverständnis, aber warum ist das Folgende kein Algorithmus zur Überprüfung der Polynomzeit? Gegeben , berechnet die Funktion selbst, den Polynomialzeit-Algorithmus, und das Rück "richtig" , wenn . Ist es möglich, dass Sie falsch verstanden oder der Professor falsch geschrieben hat und stattdessen sagen wollte, dass es Probleme gibt, die in der Polynomzeit überprüfbar, aber in der Polynomzeit nicht lösbar sind?

(x, y)

$(x,y)$

f (x)

$f(x)$

f (x) = y

$f(x)=y$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen "um zu sagen, dass es Probleme gibt, die in der Polynomzeit überprüfbar, aber in der Polynomzeit nicht lösbar sind?" [ref. benötigt]

T. Verron

@ T.Verron Haha ja, ich würde mich auch sehr freuen, den Beweis des Professors für diese Behauptung zu sehen;)

Lieuwe Vinkhuijzen

Antworten:

Dies ist nur möglich, wenn für einen bestimmten Eingang viele Ausgänge zulässig sind. Dh, wenn die Beziehung keine Funktion ist, weil sie die Eindeutigkeit verletzt. $R$

Betrachten Sie beispielsweise dieses Problem:

Bei (in unary dargestellt) und einem TM wird ein weiteres TM so dass und (wobei für die Codierung steht ( Gödelzahl) von in eine natürliche Zahl) $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ $\# N > n$ $\# N$ $N$

Dies zu lösen ist trivial: Fügen Sie dem TM weiterhin einige redundante Zustände hinzu , möglicherweise mit einigen Dummy-Übergängen zwischen ihnen, bis seine Codierung überschreitet . Dies ist eine grundlegende wiederholte Anwendung des Padding Lemma auf TMs. Dies erfordert Auffüllungen, von denen jede einen Zustand hinzufügen kann, daher kann dies in Polynomzeit erfolgen. $M$ $n$ $n$

Andererseits kann bei , ob eine korrekte Ausgabe für die Eingaben . Tatsächlich Überprüfung ist unentscheidbare (das Reis - Theorem gilt), und die Beschränkungs nur endlich viele verwirft s von denen. Da wir eine begrenzte Anzahl von Elementen aus einem unentscheidbaren Problem entfernen, erhalten wir immer noch ein unentscheidbares Problem. $n,M,N$ $N$ $n,M$ $L(M)=L(N)$ $\#N > n$ $N$

Sie können auch die unentscheidbare Eigenschaft ersetzen , um Variationen zu erhalten, die noch berechenbar, aber NP hart / vollständig sind. Zum Beispiel ist es bei (in unary) trivial, einen Graphen zu berechnen , in dem sich eine Klasse befindet. Mit es jedoch schwierig zu überprüfen, ob eine Klasse existiert. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

chi
quelle

Erwartet, dass dies nicht der Fall ist. Gute Antwort!

Filip Haglund

Dies beantwortet die Frage nicht. Das OP forderte ausdrücklich ein Problem an, das nicht im üblichen Sinne überprüfbar ist, wobei wir zusätzlich zu der Eingabe und der angeblichen Antwort ein Zertifikat

das die Richtigkeit der Antwort bestätigt. In Ihrem Fall ist das Zertifikat das Bit, mit dem die neue äquivalente Turing-Maschine nicht deterministisch generiert wird. Mit

und

ist es einfach zu überprüfen, ob

der Maschine

. Ohne

stellt sich die Frage, ob es einfach ist, harte Instanzen von (NPC-) Sprachen zu generieren, was nur in Minicrypt und Cryptomania zutrifft.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

Lieuwe Vinkhuijzen

@chi Es können nicht alle Paare

zertifiziert werden, aber die von Ihrem Algorithmus generierten Paare

können zertifiziert werden. Das Zertifikat ist das Protokoll Ihres Algorithmus, das

aus

(z. B. "Beginnen Sie mit

, fügen Sie diesen Status hinzu und fügen Sie diesen Übergang hinzu, dann ... und voilà,

!"). Wenn

ein nicht deterministischer Algorithmus ist, der bei gegebenem

immer ein zulässiges

berechnet , dann ist eine Abschrift eines Berechnungspfades von

im Allgemeinen ein Zertifikat, dass ein gegebenes

zulässig ist.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

Lieuwe Vinkhuijzen

@chi Es gibt eine kleine Nuance in der Frage: Für eine beliebige Beziehung

ist es möglich, dass nicht alle zulässigen

zertifizierbar sind, und Sie geben ein elegantes Beispiel. Bei der Frage wird jedoch nicht gefragt, ob zulässige, aber nicht überprüfbare Beziehungen bestehen (die Antwort lautet " Ja" in Ihrem Beispiel). Stattdessen wird gefragt, ob wir einen Algorithmus haben können, der zulässige, nicht überprüfbare Ergebnisse liefert. Die Antwort hier muss wegen des obigen Arguments nein sein .

R

$R$

y

$y$

Lieuwe Vinkhuijzen

@chi Ich weiß nicht, was das OP zu fragen beabsichtigt, aber ich fand Ihre Antwort sehr aufschlussreich, trotzdem habe ich etwas gelernt! Imo kann die Frage so gelesen werden, wie Sie es tun, oder genauso plausibel wie " Gibt es Einwegfunktionen? " (vielleicht) oder " Sind schwierige Fälle von NP-Problemen leicht zu erzeugen? " (Ich hoffe es für RSA), oder so wie ich es gelesen habe, als " Ist ? $NP\subsetneq P$ " (nein).

Lieuwe Vinkhuijzen

Dies ist nur eine Ausarbeitung des ersten Satzes von @ chis Antwort, da ich es nicht offensichtlich fand.

Die Idee ist, wenn Sie einen Algorithmus haben, der die Antwort auf ein Problem in der Polynomzeit findet, dann gibt es zwei Möglichkeiten:

Sie haben zuvor (mathematisch) bewiesen, dass die Ausgabe des Algorithmus eine Lösung des Problems darstellt. In diesem Fall bilden die Schritte des Algorithmus selbst den Beweis für die Richtigkeit.
Sie haben einen anderen Algorithmus, um zu überprüfen, ob die Ausgabe tatsächlich eine Lösung ist. In diesem Fall müssen Sie diesen Algorithmus ausführen (andernfalls würden Sie unter Fall 1 fallen), was impliziert, dass Sie dies in polynomieller Zeit tun.

Daher kann es kein solches Problem geben.

Mehrdad
quelle

Ich verstehe Nr. 2 nicht. Was bedeutet, dass der unterschiedliche Algorithmus in polynomialer Zeit abläuft?

Albert Hendriks

@AlbertHendriks: Wenn der Prüfer nicht in Polynomzeit ausgeführt wurde, konnte der ursprüngliche Löser nicht behaupten, in Polynomzeit eine korrekte Lösung gefunden zu haben, da er den Prüfer ausführen muss, um sicherzustellen, dass seine Lösung korrekt ist.

Mehrdad