El problema del examinador (generación uniforme de instancias / respuestas de decisiones SAT)

El asistente de enseñanza de un curso ha logrado escribir un programa que (determinísticamente) genera preguntas de examen difíciles. Ahora, le gustaría escribir un programa que genere las respuestas correspondientes. El problema del examinador pregunta si esto siempre es posible; la conjetura de examinador afirma que, suponiendo, , es no : dar con problemas es más fácil que subir con sus soluciones.$\mathsf{P} \neq \mathsf{NP}$

Más formalmente, dejemos que sea ​​una máquina de Turing determinista que, en la entrada 1 n , genera en tiempo polinomial una fórmula booleana de tamaño n . Me gustaría saber si, para todos esos M , existe una máquina de Turing de tiempo polinomial determinista M ' que, en la entrada 1 n , genera " 1 " si M ( 1 n ) tiene una asignación satisfactoria y " 0 " en caso contrario .$M$$1^n$$n$$M$$M'$$1^n$$1$$M(1^n)$$0$

Suponiendo , ¿ya se ha hecho o respondido esta pregunta? Si no se responde, ¿qué tipos de suposiciones adicionales ( por ejemplo , funciones unidireccionales) podrían influir en el resultado? Salvo cualquiera de los anteriores, mi "conjetura" es que la TM "contestadora" no siempre existe, pero ¿cuál es su intuición?$\mathsf{P} \neq \mathsf{NP}$

¡Gracias!

La pregunta que está haciendo es equivalente a unario NP = unario P, que a su vez es equivalente a NE = E, por relleno.

Desde el título, tal vez quisiste preguntar si es posible generar pares de entrada / salida de modo que la distribución en las entradas sea "difícil". La posibilidad de hacer esto se encuentra en algún punto entre P NP y existen funciones unidireccionales.$\ne$

En modelos computacionales restringidos, se sabe que esto es posible. Por ejemplo, uno puede generar pares de entrada / salida para las funciones de paridad o mayoría en AC 0 o menos. Ver La complejidad de las distribuciones .$^0$

$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$ Si:

$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)}$

si $\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$

Tenemos que aclarar lo que queremos decir con que la instancia es difícil, ya que cualquier instancia en sí misma es (teóricamente) fácil, ya que puede resolverse mediante el algoritmo que siempre dice sí o el algoritmo que siempre dice que no. Me parece que trataste de solucionar este problema imponiendo uniformidad. Pensando en términos criptográficos, sin cierta información que no se revela al adversario, no tiene sentido ocultar el resto de la computación, ya que el adversario puede simular el protocolo.

$n$$n$

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

O más formalmente,

$A\in \mathsf{PF}$$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)}$$

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

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

Véanse también los capítulos 29 y 30 del libro de Jan Krajicek "Forzar con variables aleatorias", 2011 sobre generadores de complejidad de prueba .