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 ) 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.
fuente
Respuestas:
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 ) METRO′ norte METRO X norte METRO norte2 norte3
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 3METRO X t = O ( 1 ) METRO′ O ( n2) METRO METRO′ norte3
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 )METRO X METRO′ O ( n2) O ( n3)
fuente
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.PAGS H
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 ) METRO( x ) ↓ METRO X M∗
Ahora observamos las siguientes implicaciones:
y
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) P H □
fuente
fuente
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).
fuente
Para probar esto, elija un completo , con tiempo polinómico computable (para números binarios). φ φ (x)⇔ ∃ k ∀ mΣ02 φ ψφ(x)⇔∃k∀mψ(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 < nk n ∀m<nψ(x,k,m)
n2
n 2
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 2c ≤n2+c Π01 Σ02
fuente
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
fuente
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:
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. □
fuente