Das Problem des Prüfers (einheitliche Generierung von SAT-Entscheidungsinstanzen / -antworten)

11

Der Lehrassistent eines Kurses hat es geschafft, ein Programm zu schreiben, das (deterministisch) schwierige Prüfungsfragen erzeugt. Jetzt möchte sie ein Programm schreiben, das die entsprechenden Antworten generiert. Das Problem des Prüfers fragt, ob dies immer möglich ist. der Prüfer Vermutung besagt , dass, unter der Annahme, , ist es nicht : Probleme nach oben kommt , ist einfacher als mit ihren Lösungen kommen.PNP

Formal sei eine deterministische Turingmaschine, die bei Eingabe in Polynomzeit eine Boolesche Formel der Größe . Ich würde gerne wissen, ob es für all diese eine deterministische Polynomzeit-Turingmaschine , die bei Eingabe " " ausgibt, wenn eine zufriedenstellende Zuordnung und " " hat " Andernfalls.1 n n M M ' 1 n 1M1nnMM1n1M(1n)0

Angenommen, , wurde diese Frage bereits gestellt oder beantwortet? Wenn nicht beantwortet, welche zusätzlichen Annahmen ( z. B. Einwegfunktionen?) Könnten sich auf das Ergebnis auswirken? Abgesehen von den oben genannten ist meine "Vermutung", dass das "antwortende" TM nicht immer existiert, aber was ist Ihre Intuition?PNP

Vielen Dank!

usul
quelle
Lassen Sie mich sicherstellen, dass die Quantifizierer korrekt sind. Fragen Sie sich, ob "für alle ein M 'existiert , so dass M ' die Ausgabe von M effizient lösen kann " wahr ist? MMMM
Tyson Williams
@TysonWilliams: Ja, ich habe den Wortlaut leicht bearbeitet, um dies zu verdeutlichen. Ihre Aussage sollte meiner Meinung nach meiner entsprechen!
Usul
1
Wie Emanuele hervorhebt, ist dies wahrscheinlich nicht das, wonach Sie wirklich suchen. Sie möchten wahrscheinlich Instanz-Lösungs-Paare generieren, bei denen das Lösen der Instanz "schwierig" ist. Möglicherweise im Zusammenhang mit dem, wonach Sie suchen: 1. Davids Antwort hier und 2. Abschnitt 6 von Stephen A. Cook und David G. Mitchell, " Harte Beispiele für das Problem der Erfüllbarkeit finden: Eine Umfrage ", 1997
Kaveh,

Antworten:

12

Die Frage, die Sie stellen, entspricht durch Auffüllen unary NP = unary P, was wiederum NE = E entspricht.

Vielleicht wollten Sie anhand des Titels fragen, ob es möglich ist, Eingabe / Ausgabe-Paare so zu generieren, dass die Verteilung auf die Eingaben "hart" ist. Die Möglichkeit, dies zu tun, liegt irgendwo zwischen P NP und Einwegfunktionen.

In eingeschränkten Rechenmodellen ist bekannt, dass dies möglich ist. Beispielsweise kann man Eingabe / Ausgabe-Paare für die Paritäts- oder Mehrheitsfunktionen in AC 0 oder darunter erzeugen . Siehe Die Komplexität von Verteilungen .0

Manu
quelle
1
Können Sie erklären, warum es gleichwertig ist? ... Mit "einheitlich" meine ich "einheitliches Berechnungsmodell" - wenn wir die Frage nach Schaltkreisen stellen würden, wäre die Antwort trivial ja : Jedes würde entweder eine Eins oder eine Null fest codieren, je nachdem, ob M. n ist erfüllbar oder nicht. MnMn
Usul
4
Jedes gibt eine Zählsprache in NP an: L M = { 1 n : M ( 1 n )  ist erfüllbar. } . Wenn also unary-NP gleich unary-P ist, dann ist M ' die Maschine, die über L M entscheidet . In der anderen Richtung nehmen Sie eine beliebige Zählsprache in NP und nehmen Sie M als die Maschine, die sie auf SAT reduziert. Wenn M ' existiert, dann ist die Tally-Sprache auch in P, also unär P = unär NP. Für die zweite Äquivalenz können Sie Hartmanis et al. (aber eine Richtung ist sehr einfach) dl.acm.org/citation.cfm?id=808769MLM={1n:M(1n) is satisfiable.}MLMMM
Sasho Nikolov
4

Frage: Lassen Sie Formeln erzeugen. Gehört { M ( 1 n ) n NM ( 1 n ) S A T } zu P ?MPF{M(1n)nNM(1n)SAT}P

succinctSATE Ja:

1nnO(1)

φ=M(1n)n|φ|φlgn+O(1)MnsuccintSATE2O(lgn)=nO(1)

Ja succinctSATE

MPFCMC

{M(1n)nNM(1n)SAT}PsuccinctSAT

SAT

Wir müssen klären, was wir damit meinen, dass die Instanz hart ist, da jede Instanz für sich (theoretisch) einfach ist, da sie entweder durch den Algorithmus gelöst werden kann, der immer Ja sagt, oder durch den Algorithmus, der immer Nein sagt. Es scheint mir, dass Sie versucht haben, dieses Problem zu umgehen, indem Sie Einheitlichkeit auferlegt haben. In kryptografischen Begriffen zu denken, ohne einige Informationen, die dem Gegner nicht offenbart werden, macht es keinen Sinn, den Rest der Berechnung zu verbergen, da der Gegner das Protokoll simulieren kann.

nn

A
k{0,1}n
φkwk
D
A

Oder formeller:

APFDP/polySAT(A(k)1)=A(k)2k

Prk{0,1}n{D(A(k)1)=SAT(A(K)1)}<1poly(n)

kφkA(k)2

ff(x)=yfyφf,y(x)xφf,y(x)SATff

Siehe auch Kapitel 29 und 30 von Jan Krajiceks Buch "Forcing with Random Variables", 2011 über Proof Complexity Generators .

Kaveh
quelle
M