¿Los atributos indecidibles de P plantean una obstrucción para decidir P versus NP? (respuesta: tal vez)

Se hacen cinco preguntas vinculadas, y se espera una sola respuesta integrada:

• P1: ¿Existen lenguajes que son reconocidos únicamente por aquellas máquinas de Turing en  cuyos exponentes de tiempo de ejecución son indecidibles ?$L$$P$
• P2: ¿Pueden construirse finitos ejemplos de estas máquinas de Turing?
• P3: ¿Se pueden crear instancias concretas de estas máquinas de Turing? ( p . ej. , mediante oráculos que los "adivinan" en lugar de construirlos finitamente).
• P4: ¿Qué otros atributos de P (además de los exponentes de tiempo de ejecución) se sabe actualmente que son indecidibles? ¿Para qué atributos de está abierta esta pregunta?$P$
• P5: ¿Los atributos indecidibles de plantean una obstrucción a la capacidad de decisión de ?P ≠ N P$P$$P \ne NP$

Observe cuidadosamente la palabra "únicamente" en Q1 (que excluye la respuesta sugerida de Lance Fortnow).

Conclusiones y conversión a Wiki de la comunidad

• La pregunta formulada, "¿Los atributos indecidibles de P suponen una obstrucción para decidir P versus NP?", Es abierta y se cree que es difícil, al igual que numerosas preguntas específicas (como Q1-4 anteriores) que están naturalmente asociadas a ella.

• La monografía de 1978 de Juris Hartmanis, Computaciones factibles y propiedades de complejidad comprobables, proporciona una buena entrada a la literatura y (aparentemente) no se ha publicado ninguna revisión desde Hartmanis.

• Esta clase de preguntas está suficientemente inexplorada para que el desafío de encontrar pruebas rigurosas esté íntimamente mezclado con el desafío de elegir buenas definiciones iniciales.

• Los comentarios reflexivos y los bocetos de prueba perspicaces proporcionados por Travis Service y Alex ten Brink son reconocidos y apreciados.

Debido a que la pregunta está abierta, y porque se está discutiendo en múltiples hilos matemáticos de weblog ( 1 , 2 , 3 , 4 , 5 , 6 ), esta pregunta se ha marcado para su conversión a Wiki de la comunidad.

Actualización II y resumen

Me he dado cuenta de que la monografía de 1978 de Juris Harmanis Cálculos factibles y propiedades de complejidad comprobables pueden leerse como una respuesta en profundidad a Q1–5 . Además, los bocetos de prueba (excelente) Q1 y Q4 proporcionados a continuación por Travis Service y Alex ten Brink proporcionan una afirmación moderna y una extensión de las conclusiones generales de Hartmanis que:

Los resultados sobre la complejidad de los cálculos cambian radicalmente si consideramos solo las propiedades de los cálculos que pueden probarse formalmente (énfasis de Hartmanis) ...

Por lo tanto, deberíamos esperar que los resultados sobre la optimización de todos los programas que computan la misma función que un programa dado difieran de los resultados de optimización sobre todos los programas que pueden probarse formalmente que son equivalentes al programa dado. ...

[Deberíamos] considerar la posibilidad de que este famoso problema [ ] no pueda resolverse en una teoría matemática formalizada, como la teoría de conjuntos.$P\overset{?}{=}NP$

Es evidente tanto por la monografía de Hartmanis como por las respuestas proporcionadas por Travis y Alex, que Q1-5 están considerablemente más allá del estado actual de la teoría de la complejidad. Además, estas preguntas / respuestas son evidentemente lo suficientemente sutiles como para requerir ajustes de definición cuidadosos y justificar exposiciones de longitud de monografía ... que espero que no desanime a las personas a publicar más respuestas. :)

Para una discusión técnica adicional, vea la respuesta de Joel David Hamkins en MathOverflow a la pregunta ¿Puede un problema ser simultáneamente tiempo polinómico e indecidible? (recomendado por Alex ten Brink).

Si en la monografía de Hartmanis se sustituye por "cálculo de funciones" la frase "simulación de dinámica", el resultado puede leerse como un tratado sobre los límites teóricos de la complejidad de la ingeniería de sistemas ... esta es la razón práctica por la que los ingenieros se preocupan por estos cuestiones.

Oded Goldreich expresó recientemente una opinión contraria a la de Hartmanis en una carta al editor del CACM titulada "Sobre la complejidad computacional" :

Desafortunadamente, actualmente carecemos de buenas respuestas teóricas a la mayoría de las preguntas naturales con respecto a la computación eficiente. Este no es el caso porque hacemos las preguntas equivocadas, sino porque estas preguntas son muy difíciles.

Es (por supuesto) perfectamente concebible que tanto las opiniones de Hartmanis como las de Goldreich demuestren ser correctas, por ejemplo, una prueba formal de la indecidibilidad de la separabilidad de PvsNP podría considerarse razonablemente como validación de ambos puntos de vista.

Actualización I

Los comentarios pensativos (a continuación) de Travis Service y Alex ten Brink sugieren (en efecto) que en la Q1 la frase "indecidible" no es sinónimo de "no verificable" y que las respuestas a la Q2-5 pueden depender de esta distinción. No está del todo claro (para mí) qué opción de definición conduciría a los teoremas más fuertes y, además, capturar mejor nuestra intuición de la clase P. Las respuestas y comentarios que aborden esta pregunta son bienvenidos.

Un comentario de Felix Klein en su Matemática elemental desde un punto de vista avanzado: Geometría (1939) viene a la mente:

Otro ejemplo de un concepto que ocurre con más o menos precisión en la percepción ingenua del espacio, que debemos agregar como suplemento a nuestro sistema de geometría, es la noción de una curva (arbitraria) . Cada persona cree que sabe qué es una curva hasta que haya aprendido tantas matemáticas que las innumerables anormalidades posibles las confunden.

Al igual que con las curvas, con los lenguajes aceptados por las máquinas de Turing en  ... lo que una vez me pareció (para mí) la más simple y natural de todas las clases de complejidad ahora me confunde por los atributos (incontables) no verificables y / o indecidibles de sus miembros. . La gran motivación para preguntar Q1–5 fue encontrar un camino a través de este matorral confuso, ¡pero las respuestas dadas hasta ahora (por Travis Service y Alex ten Brink) han proporcionado más motivos para la confusión!$P$

La generación de matemáticos de Klein trabajó arduamente para encontrar buenas definiciones para las curvas y otros elementos fundamentales de la teoría de conjuntos, la geometría y el análisis. Se puede encontrar una descripción general de nivel elemental en la discusión de Wikipedia sobre la Esfera con Cuernos de Alexander

      
      Una incrustación de una esfera en R3

Durante el siglo XX, el análisis de "variedades salvajes" como la esfera de Alexander ayudó a aclarar las distinciones entre las variedades topológicas, las variedades continuas por partes y las variedades diferenciales. Del mismo modo, en el siglo XXI, quizás los refinamientos de las definiciones asociadas a ayudarán a domar los lenguajes salvajes y las máquinas Turing salvajes de ... aunque especificar refinamientos adecuados no será una tarea fácil.$P$$P$

Antecedentes

Estas preguntas vinculadas surgen de las preguntas wiki de la comunidad MathOverflow " ¿Cuáles son los problemas indecidibles de Turing más atractivos en matemáticas? " Y " ¿Qué nociones se usan pero no están claramente definidas en las matemáticas modernas? " En particular, Colin Tan solicitó que la pregunta anterior publicado como una pregunta separada.

Para obtener información técnica, consulte la pregunta de TCS StackExchange " ¿Los límites de tiempo de ejecución en P son decidibles? ", En particular la prueba concisa de Emanuele Viola de que la respuesta es "no". Tenga en cuenta también que Juris Hartmanis prueba resultados similares en su monografía Cálculos factibles y propiedades de complejidad comprobables (1978).

El weblog de Lance Fortnow / Bill GASARCH de esta semana Computational Complexity está organizando su encuesta " ¿ o no?$P=NP$ " : La quinta y última pregunta formulada invita a comentar la pregunta de Fortnow / GASARCH.

Para la pregunta 1 la respuesta es no. Sea un lenguaje en P y sea M cualquier tiempo polinomial que sea una máquina de Turing que reconozca L (cuyo tiempo de ejecución se supone indecidible). Para cada k ∈ N, sea M k la máquina de Turing que en la entrada x de longitud n primeros bucles para n k pasos, luego ejecuta M en x para n k + k pasos y acepta si M acepta x (dentro de esos n k + $L$$P$$M$$L$$k \in \mathbb{N}$$M_k$$x$$n$$n^k$$M$$x$$n^k + k$$M$$x$$n^k + k$pasos) y rechaza lo contrario. El tiempo de ejecución de es Θ ( n k ) para cada k .$M_k$$\Theta(n^k)$$k$

Dado que ejecuta en tiempo polinómico, hay algo de k ′ ∈ N tal que M se ejecuta en O ( n k ′ ) (incluso si no sabemos qué es k ′ ) y, por lo tanto, para todos los k lo suficientemente grandes, M k reconoce L y tiene un tiempo de ejecución decidible.$M$$k' \in \mathbb{N}$$M$$O(n^{k'})$$k'$$k$$M_k$$L$

EDITAR

Creo que la siguiente respuesta está más en el espíritu de lo que el póster original pretendía con la pregunta 1.

Teorema: existe un lenguaje tal que si N es una máquina de Turing que decide L , al menos uno de los siguientes es cierto:$L \in P$$N$$L$

1) No existe una prueba de que acepta L , o$N$$L$

2) No existe una prueba de que detenga en f ( n ) pasos (para cualquier función f ( n ) ).$N$$f(n)$$f(n)$

Boceto de prueba: Sea una máquina de Turing que no se detenga en la cinta en blanco y para la cual no exista una prueba de que M no se detenga en la cinta en blanco (Independence resulta en Computer Science por Hartmanis y Hopcroft muestra que tal M puede ser encontrado efectivamente).$M$$M$$M$

Deje .$L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$

Como no se detiene, L es, de hecho, el lenguaje vacío, pero no hay prueba de ello (ya que eso demostraría que M no se detiene).$M$$L$$M$

Que sea ​​cualquier máquina de Turing. Si existe una prueba de que N decide L y una prueba de que N se ejecuta en f ( n ) pasos, la ejecución de N cuando se ejecuta en la entrada 1 proporciona una prueba de que M se detiene (es decir, si N acepta) o que M lo hace no detener (es decir, si N rechaza). Por lo tanto, si N decide provably L entonces N tiempo de ejecución 's no es decidible y viceversa.$N$$N$$L$$N$$f(n)$$N$$1$$M$$N$$M$$N$$N$$L$$N$

Sí, puede construir una máquina que requiera tiempo DTIME ( ) -DTIME ( n i ) donde i es el número de pasos que una máquina de Turing específica para detener en una cinta en blanco. Fácil de construir y construcciones similares son válidas para casi cualquier aspecto no trivial de P. Nos dice poco acerca de si P v NP es indecidible: no hay problema para probar P ≠ EXP a pesar de los mismos problemas.$n^{i+1}$$n^i$$i$$\neq$

Después de pensar más sobre el tema, creo que encontré una (posible) respuesta para su Q4 .

• P4: ¿Qué otros atributos de (además de los exponentes de tiempo de ejecución) se sabe actualmente que son indecidibles? ¿Para qué atributos de P está abierta esta pregunta?$P$$P$

Probé una variación en el teorema de Rice que responde a su pregunta para la mayoría de las propiedades. Esta vez intentaré explicarme más claramente (la respuesta de Travis Service fue mucho más clara y más general que mi respuesta anterior).

Teorema: para cualquier propiedad que tenga un conjunto no vacío de infinitos idiomas decidibles (pero no en idiomas finitos), es indecidible si una máquina de Turing decide un idioma con esa propiedad, cuando se promete que E siempre se detiene en O ( f ( n ) ) tiempo, donde f ( n ) = Ω ( n log n ) y f ( n ) = Ω ( g ( n ) ) , donde g ( $E$$E$$O(f(n))$$f(n)=\Omega(n \log n)$$f(n)=\Omega(g(n))$ es el tiempo de ejecución para que una máquina de Turing decida algún idioma con esa propiedad.$g(n)$

Recuerde que una máquina de Turing (TM a partir de ahora) decide un idioma si acepta todas las cadenas en el idioma y rechaza todas las cadenas fuera del idioma. Tenga en cuenta que podemos tomar a ser algo más que un polinomio, por lo que el teorema es más general que acaba de P .$f(n)$$P$

$S$$S$$S$$S \subseteq R$$S$

$P$$S \subseteq P$

$S$

$P(E)$$E$$P$$E$$S$$E$$(A, i)$$A$$i$$A$$A$$i$

$S$$s \in S$$S$$C$$s$$C$$g(n)$

function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

$O(n \log n)$

$P(H)$$A$$i$$A$$i$$t$$H$$X$$|X| \geq t$$H$$S$$P(H)$

$A$$i$$C$$s \in S$$P(H)$$P(H)$

Puedo responder tu Q1 en negativo, respondiendo así Q2 y Q3 en negativo. Sin embargo, no estoy seguro acerca de Q4 o Q5 .

• $L$$P$

$M$$T$$M$$T$

$T$$k$$T$$O(n^k)$$M$$k$$T$$T$$k$ $T$

$L$$P$$T$$O(n^k)$$k$$L$$M$$k$$T$

$L$$P$$T$$L$$T$

$L$$P$$M$$T$$L$$T$$L$

$L$$P$$L$$O(n^k)$$M$$n$$n^{k+1}$$n^{k+2}$$L$

$M$$P$$L$$L$$k$$M$

Aparentemente, este tipo de pensamiento sobre la indecidibilidad es bastante común, recuerdo una publicación (¿blog?) Sobre un tema muy similar: la pregunta era "¿es decidible si Pi tiene un 'último cero'", por lo que si Pi deja de tener ceros en su representación decimal si baja lo suficiente esa representación. Actualmente no sabemos si este es el caso. Es posible que ni siquiera podamos probarlo, o incluso que sea independiente de nuestros sistemas axiomáticos (y por lo tanto no demostrable). Pero, dado que la respuesta es verdadera o falsa, una TM que devuelve verdadero y una TM que devuelve falso deciden el problema en cualquier caso y, por lo tanto, el problema es decidible.

Veré si puedo encontrar esa publicación en Internet en alguna parte.

Editar:

Lo encontré en Mathoverflow .