¿Los límites de tiempo de ejecución en P son decidibles? (respuesta: no)

64

La pregunta que se hace es si la siguiente pregunta es decidible:

Problema   Dado que un entero máquina de Turing prometieron estar en P, ¿el tiempo de ejecución de con respecto a la longitud de entrada ?M M O ( n k ) nkMM O(nk)n

Una respuesta estrecha de "sí", "no" o "abierto" es aceptable (con referencias, bosquejo de prueba o una revisión del conocimiento actual), pero también son bienvenidas las respuestas más amplias.

Responder

Emanuele Viola ha publicado una prueba de que la pregunta es indecidible (ver más abajo).

Antecedentes

Para mí, esta pregunta surgió naturalmente al analizar la respuesta de Luca Tevisan a la pregunta ¿Los tiempos de ejecución para P requieren recursos EXP para el límite superior? ... se conocen ejemplos concretos?

La pregunta también se refiere a una pregunta de MathOverflow: ¿Cuáles son los problemas indecidibles de Turing más atractivos en matemáticas? , en una variación en la que la palabra "matemáticas" se cambia a "ingeniería", en reconocimiento de que la estimación del tiempo de ejecución es un problema de ingeniería omnipresente asociado a (por ejemplo) la teoría de control y el diseño de circuitos.

Por lo tanto, el objetivo general al hacer esta pregunta es obtener una mejor apreciación / intuición con respecto a qué aspectos prácticos de la estimación del tiempo de ejecución en la clase de complejidad P son factibles (es decir, requieren recursos computacionales en P para estimar), versus no factible (es decir, requieren recursos computacionales en EXP para estimar), versus formalmente indecidible.

--- editar (post-respuesta) ---

He agregado el teorema de Viola a la wiki de la comunidad de MathOverflow "Atractivos problemas indecidibles de Turing". Es la primera contribución de esa wiki asociada a la clase de complejidad P; Esto da fe de la novedad, la naturalidad y el amplio alcance del teorema de Viola (y en mi humilde opinión su belleza también).

--- editar (post-respuesta) ---

La monografía de Juris Hartmanis Cálculos factibles y propiedades de complejidad comprobables (1978) cubre gran parte del mismo material que la prueba de Emanuele Viola.

John Sidles
fuente
En respuesta a las preguntas formuladas en el weblog de Lance Fortnow y Bill GASARCH, bajo el tema "75 años de ciencias de la computación", comenzando "a menudo he deseado que Turing haya preguntado con seriedad:" ¿Cuáles son los procesos verificables que se pueden llevar a cabo en la computación de un número? ”... en lugar de Turing haciendo la pregunta fatídica más difícil:“ ¿Cuáles son los posibles procesos que se pueden llevar a cabo al calcular un número? ”, la siguiente pregunta será (aproximadamente)" ¿Existen máquinas de Turing que sean probables en NP, ¿cuya membresía en P es indecidible? "¡Esto es para mostrar que todavía estoy pensando en ello! :)
John Sidles
2
Aunque la prueba de Emanuele Viola es más clara, se hizo una pregunta muy similar y se respondió en Mathoverflow: mathoverflow.net/questions/28056/…
Alex ten Brink
Varias de las respuestas e ideas en este hilo resultaron relevantes para un ensayo / conjunto de preguntas que Dick Lipton ha publicado en su blog de Godel's Lost Letter ; ese conjunto de ensayo / pregunta es "Getting On Base With P = NP". URL: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp
John Sidles
Aunque los límites en P son indecidibles, no impide que uno lo intente (restringiéndose aún más). Un ejemplo si se da en esta respuesta teórica
Artem Kaznatcheev
1
Esta pregunta inspiró el siguiente artículo: arxiv.org/abs/1307.3648
David G

Respuestas:

83

El problema es indecidible. Específicamente, puede reducir el problema de detención de la siguiente manera. Dada una instancia del problema de detención, construya una nueva máquina que funcione de la siguiente manera: en entradas de longitud , simula en para pasos. Si acepta, repita pasos y pare; de lo contrario, repita pasos y pare.M n M x n M n 2 n 3(M,x)MnMxnMn2n3

Si detiene en lo hace en pasos, por lo que el tiempo de ejecución de sería . Si nunca se detiene, el tiempo de ejecución de es al menos .x t = O ( 1 ) M O ( n 2 ) M M n 3Mxt=O(1)MO(n2)MMn3

Por lo tanto, puede decidir si acepta decidiendo si el tiempo de ejecución de es u .x M O ( n 2 ) O ( n 3 )MxMO(n2)O(n3)

Manu
fuente
44
¿por qué M tiene que detenerse en x (si lo hace) en O (1) pasos?
Suresh Venkat
10
y x son fijos independientes de n . Mxn
Manu
2
Prueba muy inteligente, ¿es una variación de un resultado bien conocido o simplemente lo ideó?
Antonio E. Porreca
3
@Raphael: Esa es un área delicada, que no creo que hayamos resuelto. Algunos sitios de intercambio de pila fomentan la edición de las respuestas de otros. No tenemos una política en su contra, pero, como cuestión práctica, casi nunca lo he visto hecho. Un punto técnico: si una respuesta se edita demasiado, se convierte en wiki de la comunidad, y @Emanuele no obtendría más puntos de repetición si su respuesta fuera votada después de eso. Creo que una explicación adicional ayudaría a aclarar: @John Sidles inicialmente pensó que la promesa no se estaba usando, pero la prueba usa una promesa más fuerte : ejecuta en n 2 o n 3 , no solo P.Mn2n3
Aaron Sterling
2
@John: Mientras no se proporcione ninguna referencia publicada, considere esta guía .
Raphael
29

Esta es una reformulación de la respuesta de Emanuele Viola con el objetivo de ser más comprensible.

Mostramos que el problema dado es indecidible al reducir el problema general de detención H a él.PH

Sea cualquier instancia del problema de detención, es decir, tenemos que decidir si M ( x ) ( M se detiene en x ). Construya una máquina de Turing M que funcione de la siguiente manera:(M,x)M(x)MxM

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Ahora observamos las siguientes implicaciones:

M(x)n0N:M halts on x after at most n0 stepsy:nn0M(y) executes n2 arbitrary stepsTM(n)O(n2)

y

M(x)nN:M does not halt on x in less than n stepsy:M(y) executes n3 arbitrary stepsTM(n)Ω(n3)

Por lo tanto, . Asumiendo que P era algorítmicamente decidible, también lo sería H , lo que arroja una contradicción. H(M,x)P(M,2)PH

Rafael
fuente
12

nCn+DC,DN

Cn+D

Andrej Bauer
fuente
1
No hay escasez de comportamiento inusual por TMs de una sola cinta de poco tiempo. :)
Kaveh
4

El problema también se resolvió en mi artículo " El contenido intensivo del Teorema de Rice " POPL'2008, donde pruebo que ninguna "camarilla de complejidad" es decidible. Una camarilla de complejidad es una clase de programas de programas cerrados con un comportamiento y complejidad similares . También proporciono las condiciones necesarias para las propiedades semidecidibles.

Los programas que se ejecutan en O (n ^ k) son una camarilla de complejidad en el sentido anterior, por lo tanto, el conjunto no es decidible.

El resultado también se ha extendido recientemente a configuraciones subrecursivas (como P) por Mathieu Hoyrup: las propiedades decidibles de las funciones subrecursivas (ICALP 2016).

Andrea Asperti
fuente
2

Σ20

Σ20SSO(n2) SΣ20S

Para probar esto, elija un completo , con tiempo polinómico computable (para números binarios). φ φ (x) k mΣ20φψφ(x)kmψ(x,k,m)ψ

Entonces mantiene si la siguiente máquina es donde es la longitud de entrada (la máquina solo se preocupa por la longitud de entrada):O ( n 2 ) nφ(x)O(n2)n

para en 0 a :     si : # probado usando un ciclo de         detención,     espere pasos de detenciónn m < nkn
n 2m<nψ(x,k,m)

n2

Tenga en cuenta que para cada no demasiado pequeña , si un programa siempre se detiene (por ejemplo) pasos es -completo, pero preguntar sobre los límites de manera robusta da -completitud.n 2 + c Π 0 1 Σ 0 2cn2+cΠ10Σ20

Dmytro Taranovsky
fuente
-1

Aquí hay nuevos análisis / ángulos / resultados más sistemáticos sobre esta pregunta y otros relacionados, presentando el concepto de "verificabilidad algorítmica" y un análogo de Rice-like-thm para la teoría de la complejidad. A continuación se presenta una sección relevante del resumen y hay muchos otros teoremas relacionados relacionados con la demostrabilidad de P vs NP, etc.

  • Por qué el concepto de complejidad computacional es difícil para las matemáticas verificables / Hromkovic

    Primero, demostramos el teorema de Rice para la no demostrabilidad, afirmando que cada problema semántico no trivial sobre los programas no se puede resolver en casi todas partes en las matemáticas "AV" verificables algorítmicamente. Usando esto, mostramos que hay infinitos algoritmos (programas que son demostrablemente algoritmos) para los cuales no existen pruebas de que funcionan en tiempo polinómico o de que no funcionan en tiempo polinómico. ...

    Tenga en cuenta que, si P! = NP es demostrable en matemáticas AV, entonces para cada algoritmo A es demostrable que "A no resuelve SATISFIABILIDAD o A no funciona en tiempo polinómico". Curiosamente, finalmente mostramos que existen algoritmos para los cuales no es demostrable que no funcionen en tiempo polinómico, ni que no resuelvan la SATISFIABILIDAD. Además, hay un algoritmo que resuelve la SATISFIABILIDAD para el que no se puede demostrar en matemáticas AV que no funciona en tiempo polinómico.

    Además, mostramos que P = NP implica la existencia de algoritmos X para los cuales la afirmación "X resuelve la SATISFIABILIDAD en el tiempo polinómico" no es demostrable en matemáticas AV.

vzn
fuente
-3

La solución de Viola se puede generalizar a cualquier tiempo de ejecución (más allá de poli): puede reducir el problema de detención de la siguiente manera. Dada una instancia (M, x) del problema de detención, construya una nueva máquina M 'que funcione de la siguiente manera: en entradas de longitud n, simula M en x para pasos f (n) o hasta que M se detiene, donde f (n ) es cualquier función creciente arbitraria (mayor que constante) de n. (Obs .: M 'lee gradualmente la entrada, para evitar perder tiempo lineal [O (n)] solo para leer innecesariamente toda la entrada, si es lo suficientemente grande y M se detiene).

Si M se detiene en x, lo hace en pasos T = O (1), por lo que el tiempo de ejecución de M 'sería O (1). Si M nunca se detiene, el tiempo de ejecución de M 'es O (n ^ 2 * f (n)).

Por lo tanto, puede decidir si M acepta x decidiendo si el tiempo de ejecución de M 'es O (1) u O (n ^ 2 * f (n)).

Entonces, el código auxiliar de Raphael se puede generalizar en consecuencia mediante:

Sea (M, x) cualquier instancia del Problema de detención, es decir, tenemos que decidir si M se detiene en x. Construya una máquina de Turing determinista (DTM) M * que funcione de la siguiente manera:

  1. M * (entrada) = {
  2. n: = 0
  3. Lee el primer símbolo de la entrada
  4. Lazo:
  5. n: = n + 1
  6. Simule M (x) para f (n) pasos o hasta que M (x) se detenga
  7. Lea el siguiente símbolo de la entrada
  8. Haga un bucle hasta el final de la entrada o hasta que M (x) se haya detenido
  9. }

Ahora observamos las siguientes implicaciones:

M se detiene en x después de a lo sumo k (constantes) pasos => T (M *) = O (1) y

M nunca se detiene en x => T (M *) = O (n ^ 2 * f (n))

Por lo tanto, incluso decidir si el tiempo de ejecución de un DTM arbitrario es simplemente mayor que constante es tan difícil como detener el problema. □

André Luiz Barbosa
fuente
2
1) Utilice LaTeX. 2) ¿Cuál es la nueva contribución a esta pregunta? 3) Su razonamiento es defectuoso. Simular lleva tiempo , hasta ciertamente no puede ejecutarse en tiempo constante. O ( n ) M MO(n)M
Raphael
Para n lo suficientemente grande, si M (x) se detiene, entonces su simulación también se detiene y vuelve a M * dentro de n0 (constantes) pasos.
André Luiz Barbosa