Problem egzaminatora (jednolite generowanie instancji / odpowiedzi decyzji SAT)

Asystentowi kursu udało się napisać program, który (deterministycznie) generuje trudne pytania egzaminacyjne. Teraz chciałaby napisać program, który generuje odpowiednie odpowiedzi. Problem egzaminatora pyta, czy jest to zawsze możliwe; przez egzaminatora Hipoteza stwierdza, że zakładając, $\mathsf{P} \neq \mathsf{NP}$ , to nie : wymyślanie problemów jest łatwiejsze niż wymyślanie swoich rozwiązań.

Bardziej formalnie, niech $M$ będzie deterministyczną Maszyną Turinga, która na wejściu $1^n$ generuje w czasie wielomianowym logiczną formułę wielkości $n$ . Chciałbym wiedzieć, czy dla wszystkich takich $M$ istnieje deterministyczna wielomianowa maszyna Turinga $M'$ która na wejściu $1^n$ wyprowadza „ $1$ ”, jeśli $M(1^n)$ ma zadowalające przypisanie, a „ $0$ ” w przeciwnym razie .

Zakładając , czy to pytanie zostało już zadane lub na które udzielono odpowiedzi? Jeśli nie zostanie udzielona odpowiedź, jakie dodatkowe założenia ( np. Funkcje jednokierunkowe?) Mogą wpłynąć na wynik? Z wyjątkiem któregokolwiek z powyższych, moja „hipoteza” jest taka, że ​​TM odpowiadająca nie zawsze istnieje, ale jaka jest twoja intuicja?$\mathsf{P} \neq \mathsf{NP}$

Dzięki!

Pytanie, które zadajesz, jest równoważne jednemu NP = unarnemu P, który z kolei jest równoważny NE = E, poprzez wypełnienie.

Z tytułu może chciałeś zapytać, czy można wygenerować pary wejścia / wyjścia, tak że rozkład na wejściach jest „trudny”. Możliwość zrobienia tego leży gdzieś pomiędzy P NP a funkcjami jednokierunkowymi.$\ne$

W ograniczonych modelach obliczeniowych wiadomo, że jest to możliwe. Np. Można wygenerować pary wejścia / wyjścia dla funkcji parzystości lub większości w AC 0 lub niższej. Zobacz Złożoność dystrybucji .$^0$

Pytanie: Niech wygeneruje formuły. Czy { M ( 1 n ) ∣ n ∈ N ∧ M ( 1 n ) ∈ S A T } należy do P ?$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$ Tak:

Założenie dotyczące generowania wzorów w czasie wielomianowym od oznacza, że ​​wzór można podać zwięźle . Chcesz zdecydować o ich spełnieniu w czasie n O ( 1 ) .$1^n$$n^{O(1)}$

Dany możemy znaleźć nw czasie wielomianowym w | φ | . Następnie φ można podać zwięźle wbitach lg n + O ( 1 ) przy użyciu M i n . Można używamy S U c c i n t S T algorytm E zdecydować, to w czasie 2 O ( lg n ) = N $\varphi = M(1^n)$$n$$|\varphi|$$\varphi$$\lg n+O(1)$$M$$n$$succintSAT$$\mathsf{E}$ .$2^{O(\lg n)} = n^{O(1)}$

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

Niech st biorąc pod uwagę obwód C w jedności , M oblicza ciąg zwięźle zakodowany przez C i zwraca wynik, jeśli jest to wzór, a ⊥ w przeciwnym razie.$M \in \mathsf{PF}$$C$$M$$C$$\bot$

Załóżmy, że należą do P . Aby rozwiązać s U c c i n c t S A T opisali danej formuły w zwięzły jednoargumentowy a następnie korzystając z założenia do rozwiązania.$\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$$\mathsf{P}$$succinctSAT$

Pytanie: Czy możemy wygenerować w parach instancji rozwiązanie czas wielomianowe dla tak, że instancja jest trudna?$SAT$

Musimy wyjaśnić, co rozumiemy przez to, że instancja jest trudna, ponieważ każda instancja sama w sobie jest (teoretycznie) łatwa, ponieważ można ją rozwiązać za pomocą algorytmu, który zawsze mówi tak, lub algorytmu, który zawsze mówi nie. Wydaje mi się, że próbowałeś obejść ten problem, nakładając jednolitość. Myśląc kryptograficznie, bez pewnych informacji, które nie zostaną ujawnione przeciwnikowi, nie ma sensu ukrywać reszty obliczeń, ponieważ przeciwnik może symulować protokół.

Załóżmy, że mamy algorytm czasu wielomianowego, który generuje pary instancja-rozwiązanie. Przeciwnik może użyć tego samego algorytmu, aby znaleźć odpowiedź, jeśli zna a znalezienie n nie jest trudne ze wzoru. Bardziej rozsądnym sposobem jest użycie losowo wybranego tajnego klucza, aby obejść ten problem i rozluźnić warunek twardości, aby być probabilistycznym: żaden algorytm wielomianowy nie może znaleźć rozwiązania z dużym prawdopodobieństwem (bez znajomości tajnego klucza).$n$$n$

Czy jest skuteczny (deterministyczny) algorytm taki sposób, że dana losowo wybiera k ∈ { 0 , 1 } n , generuje parę Instancje SAT cp k i jego odpowiedź wag K , tak że nie jest efektywny (probabilistyczny / niejednorodny) algorytm przeciwnik D potrafi poprawnie rozwiązać wystąpienia SAT wygenerowane przez A z nieistotnym prawdopodobieństwem?$A$
$k \in \{0,1\}^n$
$\varphi_k$$w_k$
$D$
$A$

Lub bardziej formalnie

Czy istnieje taki, że dla wszystkich D ∈ $A\in \mathsf{PF}$ , taki, że SAT(A(k ) 1 )=A(k ) 2 dla wszystkichki P r k ∈ { 0 , 1 } n {D(A(k ) 1 )=SA$D \in \mathsf{P/poly}$$SAT(A(k)_1) = A(k)_2$$k$

$$\mathsf{Pr}_{k \in \{0,1\}^n} \{ D(A(k)_1) = SAT(A(K)_1) \} < \frac{1}{poly(n)}$$

Łatwo zauważyć, że taką funkcję można przekształcić w funkcję jednokierunkową, tak jakby łatwo było znaleźć z φ k, wówczas możemy znaleźć odpowiedź, obliczając A ( k ) 2 .$k$$\varphi_k$$A(k)_2$

Z drugiej strony, niech będzie funkcją jednokierunkową. Możemy wyrazić f ( x ) = y jako obwód wielkości wielomianowej, ponieważ f można obliczać w czasie wielomianowym (i możemy przekształcić go w formułę wprowadzając nowe zmienne dla wszystkich bramek i lokalnie egzekwując warunek poprawności obliczeń jak w tłumaczeniu Tsiena). Rozważmy y jako parametr i oznaczmy wynikową formułę jako φ f , y ( x ) . Możemy zapytać, czy jest jakieś x, które spełnia φ f , y ( x $f$$f(x)=y$$f$$y$$\varphi_{f,y}(x)$$x$$\varphi_{f,y}(x)$. Każdy algorytm wielomianowy rozwiązujący te instancje z prawdopodobieństwem nieistotnym zniszczy funkcję jednokierunkową f . Wykorzystuje to jednak fakt, że przeciwnik musi znaleźć świadka, a nie tylko fakt, że formuła jest zadowalająca lub nie (ale myślę, że możemy poradzić sobie z tym problemem, używając twardego f ).$SAT$$f$$f$

Zobacz także rozdziały 29 i 30 książki Jana Krajicka „Forcing with Random Variables”, 2011 na temat generatorów złożoności dowodu .