Dado un algoritmo de tiempo polinómico, ¿podemos calcular un límite de tiempo polinómico explícito sólo a partir del programa?

Question

Pregunta. Dado un programa de máquina de Turing $e$ que se garantiza que se ejecuta en tiempo polinómico, ¿podemos encontrar computacionalmente encontrar tal polinomio?

En otras palabras, ¿hay una función computable $e\mapsto p_e$ , de tal manera que siempre que $e$ es un programa de máquina de Turing que se ejecuta en tiempo polinómico, entonces $p_e$ ¿es un límite de tiempo polinómico? Es decir, $p_e$ es un polinomio sobre los enteros en una variable y programa $e$ en cada entrada $n$ se ejecuta en un tiempo máximo de $p_e(|n|)$ , donde $|n|$ es la longitud de la entrada $n$ .

(Tenga en cuenta que no impongo ningún requisito a $p_e$ cuando $e$ no es un programa de tiempo polinómico, y no estoy preguntando si la función $e\mapsto p_e$ es computable en tiempo polinómico, pero sino más bien, si es computable en absoluto).

En el campo de la teoría de la complejidad, es común tratar algoritmos de tiempo polinómico como si vinieran equipados con un reloj polinómico explícito, que cuenta los pasos durante el computación y que obliga a detenerse cuando se vence. Esta convención permite ciertas comodidades en la teoría. Sin embargo, en el campo de la teoría de la computabilidad, sin embargo, no se suele que un algoritmo de tiempo polinómico venga equipado con tal contador. Mi pregunta es si podemos producir computablemente producir tal contador sólo a partir del programa de la máquina de Turing de Turing.

Espero una respuesta negativa. Creo que no existe tal función computable $e\mapsto p_e$ y la pregunta es realmente sobre cómo vamos a probar esto. Pero no sé...

Por supuesto, dado un programa $e$ podemos obtener un número finito de puntos de muestra para un límite inferior en el polinomio, pero esto no parece útil. Además, parece que la lección de Teorema de Rice es que no podemos esperar calcular información no trivial mediante el programa en sí, y esto lo considero una prueba en contra de la evidencia contra una respuesta afirmativa. Al mismo tiempo, el teorema de Rice no se aplica directamente, ya que el polinomio $p_e$ no depende del conjunto o función que $e$ sino en la forma en que computa en la forma en que lo computa. Así que no estoy seguro.

Por último, permítanme mencionar que esta pregunta está relacionada con y inspirada en esta reciente e interesante pregunta de MO sobre el imposibilidad de convertir algoritmos NP en algoritmos P algoritmos . Varias de las respuestas propuestas allí dependían críticamente de si el contador de tiempo polinómico formaba parte de la entrada o no. En particular, una respuesta afirmativa a la presente pregunta lleva a una solución de esa pregunta por esas respuestas. Mi expectativa, sin embargo, es que una respuesta negativa aquí y una respuesta allí que descarte una transformación computable.

Answer 1

[Editar: Se ha corregido un error en la prueba original, gracias a un comentario de François Dorais].

La respuesta es no. Este tipo de cosas se pueden demostrar con lo que yo llamo un argumento de "tanque de gas". Primero enumerar todas las máquinas de Turing de alguna manera $N_1, N_2, N_3, \ldots$ Entonces construye una secuencia de máquinas de Turing $M_1, M_2, M_3, \ldots$ como sigue. En una entrada de longitud $n$ , $M_i$ simula $N_i$ (con la entrada vacía) hasta $n$ pasos. Si $N_i$ no se detiene en ese tiempo, entonces $M_i$ se detiene inmediatamente después del $n$ paso. Sin embargo, si $N_i$ se detiene en la primera $n$ pasos, entonces $M_i$ "se queda sin gasolina" y empieza a comportarse de forma errática, lo que en este contexto significa (digamos) que sigue funcionando durante $n^e$ pasos antes de detenerse donde $e$ es el número de pasos que $N_i$ tomó para detenerse.

Ahora bien, si tuviéramos un programa $P$ que pudiera calcular una cota superior polinómica en cualquier máquina de polittiempo, entonces podríamos determinar si $N_i$ se detiene llamando a $P$ en $M_i$ , leyendo el exponente $e$ y la simulación de $N_i$ para (como máximo) $e$ pasos. Si $N_i$ no se detiene para entonces, entonces sabemos que nunca se detendrá.

Por supuesto, esta técnica de prueba es muy general; por ejemplo, $M_i$ puede hacerse para simular cualquier $M$ mientras tenga gasolina, pero luego hace otra cosa cuando se queda sin gasolina, lo que demuestra que será indecidible si una máquina dada arbitrariamente se comporta como $M$ .

Answer 2

También se puede diagonalizar directamente contra un supuesto algoritmo de producción de límites. Digamos que $R(j)$ devuelve un polinomio cuando se ejecuta con cualquier índice $j$ de una función de tiempo polinómico como entrada.

Definir una función $B(j,n)$ como sigue. En la entrada $n$ , corre $R(j)$ para $n$ pasos. Si esto no se detiene, devuelve $0$ inmediatamente. En caso contrario, si $R(j)$ no devuelve un polinomio cuando se detiene, devuelve $0$ inmediatamente. En caso contrario, si el polinomio es $p(x)$ , desperdiciar al menos $(n+p(n))^2$ pasos y luego volver $0$ .

Tenga en cuenta que para cualquier $j$ la función $C_j(n) = \lambda n . B(j,n)$ es total y se ejecuta en tiempo polinómico, y si $R(j)$ devuelve un polinomio, entonces esto no es un límite en el tiempo de ejecución de $C_j(n)$ .

Ahora la función que toma un número $j$ y devuelve un índice para el $C_j$ es una función totalmente computable. Así que podemos utilizar el teorema de la recursión para producir un índice $k$ tal que $\phi_k(n) = C_k(n)$ . Entonces $\phi_k$ será una función de tiempo polinómico total, pero si $R(k)$ devuelve un polinomio, entonces no es un límite superior para $\phi_k$ .

Nota: El párrafo anterior requiere algo más que el enunciado habitual del teorema de recursividad, requiere algún conocimiento de la prueba para demostrar que $\phi_k$ es de tiempo polinómico. Aquí está la construcción que necesito.

Dejemos que $s(j,k)$ sea la función habitual de tiempo polinómico tal que $\phi_{s(j,k)}(n) \simeq \phi_j(k,n)$ el punto clave que necesitamos es que el tiempo de ejecución de $\phi_{s(j,k)}(n)$ está acotado polinómicamente si el tiempo de ejecución de $\phi_j(k,n)$ está acotada polinómicamente, y la primera de ellas no es menor que la segunda. Esto se puede comprobar examinando la construcción de $s$ en el modelo de cálculo elegido.

Ahora dejemos que $d$ sea el índice de la función computable $\phi_d(j,n) = B(s(j,j),n)$ obtenido por simple composición. Sea $k = s(d,d)$ . Entonces $\phi_k(n) = \phi_d(d,n) = B(k,n)$ como se desea; ésta es la prueba del teorema de recursión. Además, la aplicación de estas funciones garantiza que $\phi_k(n)$ se ejecuta en tiempo polinómico pero no más rápido que $B(k,n)$ porque cada cálculo de $\phi_k(n)$ consiste en un tiempo polinómico en $n$ invocaciones de $s$ funciones seguidas de la ejecución literal del programa para $B(k,n)$ .

Answer 3

Sólo para observar, también en vista del comentario de Carl Mummert, que utilicé técnicas muy similares en mi artículo de POPL'08 " El contenido intensional del teorema de Rice ". Llamo "camarilla de complejidad" a una clase de programas con comportamiento similar (como para Rice) y complejidad asimétrica, y demostrar que ninguna camarilla de complejidad es decidible. También doy condiciones necesarias para la semidecibilidad, en el espíritu de Rice-Shapiro.

Mi resultado también ha sido ampliado recientemente a entornos subrecursivos (como P o NP) por Mathieu Hoyrup: Las propiedades decidibles de las funciones subrecursivas (ICALP 2016).