Solucionadores NP óptimos

Arregle un problema de búsqueda NP-complete, por ejemplo, la forma de búsqueda de SAT. La búsqueda de Levin proporciona un algoritmo para resolver X que es óptimo en algún sentido. Específicamente, el algoritmo es "Ejecutar todos los posibles programas P en cola de milano en la entrada x , una vez que P devuelve la respuesta y prueba si es correcta". Es óptimo en el sentido de que dado un programa P que resuelve X con una complejidad temporal t_P (n) , la complejidad temporal t_L (n) de L satisface L X P x P y P X t P ( n ) t L ( n ) $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$$L$$X$$P$$x$$P$$y$$P$$X$$t_P(n)$$t_L(n)$$L$

donde $p$ es un polinomio fijo que depende del modelo de cálculo preciso

$L$La optimización de L puede formularse de una manera algo más fuerte. Es decir, por cada $M \subset \lbrace 0,1 \rbrace^*$ y $Q$ un programa que resuelve $X$ con la promesa $M$ en el tiempo $t^M_Q(n)$ , la complejidad del tiempo $t_L^M(n)$ de $L$ restringida a entradas en $M$ satisface

donde $q$ es un polinomio fijo. La diferencia crucial es que $t^M_Q(n)$ puede ser, por ejemplo, polinomial incluso si $P \neq NP$

La obvia "debilidad" de $L$ es el gran factor $2^{|Q|}$ en este límite. Es fácil ver que si hay un algoritmo que satisface un límite de la misma forma con $2^{|Q|}$ reemplazado por un polinomio en $|Q|$entonces $P = NP$ . Esto se debe a que podemos considerar que $Q$ es un programa que resuelve una instancia determinada de $X$ codificando la respuesta. Del mismo modo, si $2^{|Q|}$ se puede reemplazar por una función sub-exponencial de $|Q|$entonces se viola la hipótesis del tiempo exponencial. Sin embargo, la respuesta a la siguiente pregunta es menos obvia (para mí):

Suponiendo la hipótesis del tiempo exponencial y otras conjeturas bien conocidas (por ejemplo, la no degeneración de la jerarquía polinómica, la existencia de funciones unidireccionales) si es necesario, ¿hay un algoritmo resuelva st para cada y un programa que resuelve con la promesa en el tiempo , la complejidad del tiempo de restringida a entradas en satisfaceX M ⊂ { 0 , 1 } ∗ Q $A$$X$$M \subset \lbrace 0,1 \rbrace^*$$Q$$X$t M Q ( n ) t M A ( n ) A $M$$t^M_Q(n)$$t_A^M(n)$$A$$M$

$$t_A^M(n) < f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$$

donde es polinomial, es sub-exponencial y es arbitrariof $q$$f$$g$

Si la respuesta es positiva, ¿puede ser polinomial? ¿Cuál es la tasa de crecimiento de (claramente al menos exponencial bajo ETH)? Si la respuesta es negativa, ¿puede existir el polinomio si ETH está mal pero ?g f P ≠ N $f$$g$$f$$P \neq NP$

Considere el siguiente algoritmo (una variante del algoritmo de Levin):

Ejecute los primeros algoritmos en paralelo. Además, ejecute en paralelo un algoritmo de fuerza bruta que pruebe todas las soluciones posibles una por una. (Ejecute todos los algoritmos con la misma velocidad).$n$

Pare cuando uno de los algoritmos encuentre una solución.

Considere dos casos (dada una entrada de longitud ):$x$$n$

• $Q$ es uno de los primeros algoritmos. Entonces el tiempo de ejecución es .$n$$O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$

• n n $Q$ no es uno de los primeros algoritmos (por lo tanto, ). Entonces, el tiempo de ejecución está limitado por el tiempo de ejecución del algoritmo de fuerza bruta. Tenemos que el tiempo de ejecución es .$n$$n < 2^{|Q|}$$2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$

Tenemos

(Aquí, es polinomial y es doblemente exponencial en ; podemos mejorar la dependencia de de al empeorar la dependencia de de ).g ( n ) n g ( n ) n f ( n ) $f(n)$$g(n)$$n$$g(n)$$n$$f(n)$$n$