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. $\mathsf{P} \neq \mathsf{NP}$

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. $M$ $1^n$ $n$ $M$ $M'$ $1^n$ $1$ $M(1^n)$ $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? $\mathsf{P} \neq \mathsf{NP}$

Vielen Dank!

cc.complexity-theory uniformity usul
quelle

Lassen Sie mich sicherstellen, dass die Quantifizierer korrekt sind. Fragen Sie sich, ob "für alle

ein

, so dass

die Ausgabe von

effizient lösen kann " wahr ist?

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

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,

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. $\ne$

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 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

ist erfüllbar oder nicht.

M_{n}^{'}

$M'_n$

M_{n}

$M_n$

Usul

4

Jedes

gibt eine Zählsprache in NP an:

. Wenn also unary-NP gleich unary-P ist, dann ist

die Maschine, die über

entscheidet . In der anderen Richtung nehmen Sie eine beliebige Zählsprache in NP und nehmen Sie

als die Maschine, die sie auf SAT reduziert. Wenn

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=808769

M

$M$

L_{M} = {1^{n} : M (1^{n}) is satisfiable.}

$L_M =\{1^n: M(1^n) \text{ is satisfiable.}\}$

M^{'}

$M'$

L_{M}

$L_M$

M

$M$

M^{'}

$M'$

Sasho Nikolov

4

Frage: Lassen Sie Formeln erzeugen. Gehört zu ? $M\in \mathsf{PF}$ $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ $\mathsf{P}$

$succinctSAT \in \mathsf{E} \implies$ Ja:

$1^n$ $n^{O(1)}$

$\varphi = M(1^n)$ $n$ $|\varphi|$ $\varphi$ $\lg n+O(1)$ $M$ $n$ $succintSAT$ $\mathsf{E}$ $2^{O(\lg n)} = n^{O(1)}$

Ja $\implies succinctSAT \in \mathsf{E}$

$M \in \mathsf{PF}$ $C$ $M$ $C$ $\bot$

$\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ $\mathsf{P}$ $succinctSAT$

$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.

$n$ $n$

$A$
$k \in \{0,1\}^n$
$\varphi_k$ $w_k$
$D$
$A$

Oder formeller:

$A\in \mathsf{PF}$ $D \in \mathsf{P/poly}$ $SAT(A(k)_1) = A(k)_2$ $k$
${P r}_{k \in {0, 1}^{n}} {D (A (k)_{1}) = S A T (A (K)_{1})} < \frac{1}{p o l y (n)}$ $\mathsf{Pr}_{k \in \{0,1\}^n} \{ D(A(k)_1) = SAT(A(K)_1) \} < \frac{1}{poly(n)}$

$k$ $\varphi_k$ $A(k)_2$

$f$ $f(x)=y$ $f$ $y$ $\varphi_{f,y}(x)$ $x$ $\varphi_{f,y}(x)$ $SAT$ $f$ $f$

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

Kaveh
quelle

M^{'}

$M'$

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

Antworten:

Frage: Lassen Sie Formeln erzeugen. Gehört { M ( 1 n ) ∣ n ∈ N ∧ M ( 1 n ) ∈ S A T } zu P ?M∈PFM∈PFM\in \mathsf{PF}{M(1n)∣n∈N∧M(1n)∈SAT}{M(1n)∣n∈N∧M(1n)∈SAT}\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}PP\mathsf{P}

SATSATSAT

Frage: Lassen Sie Formeln erzeugen. Gehört zu ? $M\in \mathsf{PF}$ $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ $\mathsf{P}$

$SAT$