¿P contiene lenguajes cuya existencia es independiente de PA o ZFC? (Wiki de la comunidad TCS)

14

Respuesta: no conocida.

Las preguntas formuladas son naturales, abiertas y aparentemente difíciles; La pregunta ahora es una wiki comunitaria.

Visión general

La pregunta busca dividir los idiomas que pertenecen a la clase de complejidad P  , junto con las máquinas de Turing de decisión (TM) que aceptan estos idiomas, en dos subclases complementarias:

  • lenguajes gnósticos y TM (que son factibles de validar / comprender), versus
  • lenguajes y TM crípticos (que no son factibles de validar / comprender).

Definiciones: números gnósticos frente a crípticos , TM e idiomas

Dentro de los marcos de axioma PA y ZFC , distinguimos las máquinas e idiomas gnósticos de Turing crípticos de la siguiente manera:

D0   Decimos que un número real computable   es gnóstico si está asociado a un conjunto no vacío de TM, con cada TM especificada en PA como una lista explícita de números que comprende un código válido sobre una TM universal, de modo que para cualquier precisión ϵ > 0 suministrado como entrada, cada TM probablemente (en ZFC) se detiene con un número de salida o que probablemente (en ZFC) satisface r - ϵ < o < r + ϵ .rϵ>0orϵ<o<r+ϵ

Observación   Se sabe que algunos reales computables no son gnósticos (para un ejemplo concreto, ver la respuesta de Raphael Reitzig a la pregunta de jkff " ¿Hay pruebas de existencia de algoritmos no constructivos? "). Para evitar lidiar con estos números computables pero incómodos, se impone la restricción de que los exponentes de tiempo de ejecución sean computables por TM que se enumeran explícitamente en PA (en contraste con TM especificadas implícitamente en ZFC). Para una discusión más detallada, consulte la sección Consideraciones de definición (a continuación).

Ahora buscamos definiciones que capturen la intuición de que la clase de complejidad incluye un subconjunto de lenguajes crípticos a los que no se puede asignar ningún exponente de tiempo de ejecución (gnóstico) de límite inferior. P

Para mirar hacia el futuro, la definición final ( D5 ) especifica la idea de una decisión TM canónicamente críptica , cuya definición está diseñada con miras a evitar las reducciones que enmascaran (trivialmente) los cálculos crípticos mediante la superposición de cómputos epi computacionalmente superfluos. El fundamento y fuentes de esta definición de la clave se discuten más adelante - en el epígrafe Consideraciones de definición  - y las contribuciones de los comentarios de acuerdo a Timoteo Chow, Peter Shor, Sasho Nikolov, y Luca Trevisan se agradece.

D1   Dada una máquina de Turing M que se detiene para todas las cadenas de entrada, M se llama críptico si la siguiente afirmación no es demostrable ni refutable para al menos un número real gnóstico  :r0

Declaración: el tiempo de ejecución de M es con respecto a la longitud de entrada nO(nr)n

Las máquinas de Turing que no son crípticas, decimos que son TM gnósticas.

D2   Decimos que una decisión Turing machine M es eficiente si tiene un exponente de tiempo de ejecución gnóstico  tal manera que el lenguaje L que M acepta no sea aceptado por ninguna otra TM que tenga un exponente de tiempo de ejecución gnóstico menor que  r .rr

D3   Decimos que una lengua L es críptica si es aceptada por (a)  al menos una máquina Turing M es eficiente y críptica, y además (b)  ninguna TM que sea eficiente y gnóstica acepta L.

Para expresar D3 de otra manera, un lenguaje es críptico si las TM que aceptan ese lenguaje de manera más eficiente son crípticas.

Los idiomas que no son crípticos, decimos que son idiomas gnósticos .

D4   Decimos que un TM críptico es fuertemente críptico si el lenguaje que acepta es críptico.

D5   Decimos que una TM fuertemente críptica es canónicamente críptica si es eficiente.

Para expresar D5 de otra manera, cada lenguaje críptico es aceptado por un conjunto de TM de decisión canónicamente crípticas, que son las TM de decisión más eficientes que aceptan ese lenguaje.

Las preguntas formuladas

La siguiente conjetura C0 es natural y (aparentemente) abierta:

C0   La clase de complejidad P contiene al menos un lenguaje críptico.

Se hacen tres preguntas, Q1 - Q3 , de las cuales la primera es:

Q1   ¿La conjetura C0 es independiente de PA o ZFC?

Bajo el supuesto de que C0 es verdadero, ya sea demostrablemente en ZFC, o como un axioma independiente que es complementario a ZFC, dos preguntas más son naturales:

P2   ¿Se puede presentar al menos un lenguaje críptico en P de manera concreta, es decir, exhibido como un diccionario de palabras explícitas en un alfabeto finito que incluya todas las palabras de una longitud específica? Si es así, exhiba dicho diccionario.

Q3   ¿Se puede presentar concretamente al menos una decisión canónicamente críptica TM, es decir, como una descripción que permita construir una máquina física de Turing que decida (en tiempo polinómico) todas las palabras del diccionario de Q2 ? Si es así, construya una máquina de Turing de este tipo y, al computar con ella, exhiba el diccionario de lenguaje críptico de Q2 .

Consideraciones definitorias

La definición D0 implica que cada número real gnóstico es computable, pero se sabe que algunos números reales computables no son gnósticos. Para ver ejemplos, consulte las respuestas en MathOverflow de Michaël Cadilhac y Ryan Williams y en TCS StackExchange de Raphael Reitzig . De manera más general, las definiciones D0 – D5 están diseñadas para excluir referencias a exponentes de tiempo de ejecución no gnósticos.

Como se discutió en la wiki de TCS " ¿P contiene lenguajes incomprensibles? ", Las definiciones D0-D5 aseguran que cada lenguaje críptico sea aceptado por al menos un TM que es canónicamente críptico. (Tenga en cuenta también que en la presente pregunta la palabra "críptico" reemplaza a la palabra menos descriptiva "incomprensible" utilizada en la wiki).

Además, en vista de D3 (a) y D3 (b)  , no existe una reducción computacionalmente trivial de una TM canónicamente críptica a una TM gnóstica que pueda demostrar el mismo lenguaje. En particular, D3 (a) y D3 (b) obstruir los polylimiter estrategias de reducción que se describen en los comentarios de Peter Shor , y por Sasho Nikolov , e independientemente por Luca Trevisan , y obstruye demasiado el polinómicamente velocidad de reloj estrategia de reducción de Timoteo Chow , toda de los cuales enmascaran de manera similar los cálculos crípticos superponiendo un cómputo epi computacionalmente superfluo .

En general, las definiciones de "gnóstico" y "críptico" se ajustan deliberadamente para que sean robustas con respecto a las reducciones matemáticamente triviales (y es completamente posible que un ajuste adicional de estas definiciones sea deseable).

Consideraciones metodologicas

La revisión de Lance Fortnow " El estado del problema P versus NP " examina métodos para establecer la independencia (o de otro modo) de conjeturas en la teoría de la complejidad; Se desean especialmente sugerencias sobre cómo los métodos que las revisiones de Lance podrían ayudar (o no) a responder P1 .

Está claro que muchas otras preguntas son naturales. Por ejemplo, la Conjetura de Hartmanis-Stearns nos inspira a preguntarnos "¿Existen máquinas criptográficas en tiempo real de múltiples cintas de Turing? ¿Es su existencia (o no) independiente de PA o ZFC?"

Consideraciones de tipo Zeilberger

En el caso de que Q1 se responda con un "sí", entonces los oráculos que deciden pertenecer a existen fuera de PA o ZFC, y por lo tanto, un elemento esencial de la teoría moderna de la complejidad (actualmente) no se sabe que reside dentro de ningún sistema formal de lógica. P

A este respecto, la teoría de la complejidad se distingue de la mayoría de las disciplinas matemáticas, de modo que las aprensiones que Doron Zeilberger expresa en su reciente " Opinión 125: Ahora que Alan Turing cumplió 100 años, es hora de tener una mirada fresca a sus contribuciones seminales , eso hizo mucho bien pero también mucho daño "podría decirse que está bien fundado.

Las preocupaciones de Zeilberger toman forma explícita como criterio Z0    (! Q1  ) && (! C0  ), que es equivalente al siguiente criterio:

Z0:   criterio de sensibilidad de Zeilberger Las   definiciones de la clase de complejidad P   se llaman sensibles a Zeilberger si todos los lenguajes en P son demostrablemente gnósticos.

En la actualidad no se sabe si la definición de Stephen Cook de la clase de complejidad P   es sensible a Zeilberger.

Consideraciones motivacionales

Las definiciones de "gnóstico" y "críptico" se elaboran con vistas a (eventualmente) decidir conjeturas como las siguientes:

C1   Sean y N P las restricciones gnósticas de P y N P resp. Entonces P N P es demostrable o refutable en PA o ZFC.PNPPNPPNP

C2   (como se demostró explícitamente en PA o ZFC)PNP

Claramente C2   C1 , y por el contrario, es concebible que una prueba del (meta) teorema C1 pueda proporcionar una guía hacia una prueba del teorema (más fuerte) C2 . 

La motivación general es la expectativa / intuición / esperanza de que, para una distinción bien ajustada entre TM e idiomas gnósticos y crípticos, una prueba de C1 y posiblemente incluso C2 podría iluminar, e incluso tener implicaciones prácticas comparables a, presumiblemente mucho más difícil y más profundo prueba de que . PNP

Juris Hartmanis fue uno de los primeros teóricos de la complejidad en perseguir seriamente esta línea de investigación; véase , por ejemplo, la monografía de Hartmanis Cálculos factibles y propiedades de complejidad comprobables (1978).

Consideraciones nomenclaturales

Del Oxford English Dictionary (OED) tenemos:

  • gnóstico (adj)  Relacionado con el conocimiento; cognitivo; intelectual   "Ellos [los números] existen de una manera vital, gnóstica y especulativa, pero no operativa".

  • críptico (adj)  No inmediatamente comprensible; misterioso y enigmático   "En lugar de reglas simples útiles para la humanidad, [los filósofos] obstaculizan las frases oscuras y cruptick".

Aparentemente, ninguna Revisión matemática ha usado previamente la palabra "gnóstico" en ningún sentido. Sin embargo, se llama la atención sobre el reciente artículo de Marcus Kracht " Gnosis " ( Journal of Philosophical Logic , MR2802332), que utiliza el sentido OED.

Aparentemente, ninguna Revisión matemática ha utilizado la palabra "críptico", en su sentido técnico, en relación con la teoría de la complejidad. Sin embargo, se llama la atención al artículo de Charles H. Bennett " Profundidad lógica y complejidad física " (en The Universal Turing Machine: A Half-Century Survey , 1988) que contiene el pasaje

Otro tipo de complejidad asociada con un objeto sería la dificultad, dado el objeto, de encontrar una hipótesis plausible para explicarlo. Los objetos que tienen este tipo de complejidad podrían llamarse "crípticos" : encontrar un origen plausible para el objeto es como resolver un criptograma.

Consideraciones de naturalidad, apertura y dificultad.

La naturalidad de estas preguntas ilustra la tesis de la monografía de Juris Hartmanis Cálculos factibles y propiedades de complejidad comprobables (1978) que:

"Los resultados sobre la complejidad de los algoritmos cambian radicalmente si consideramos solo las propiedades de los cálculos que pueden probarse formalmente".

La apertura y la dificultad de estas preguntas están en consonancia con la conclusión de la revisión de Lance Fortnow " El estado del problema P versus el problema NP " (2009) que:

"Ninguno de nosotros comprende realmente el problema P versus NP, solo hemos comenzado a despegar las capas alrededor de esta pregunta cada vez más compleja".

Guia Wiki

Particularmente buscados son los ajustes de definición y las estrategias de prueba específicamente relacionadas con las preguntas Q1-Q3 e iluminando ampliamente las conjeturas de tipo Hartmanis C1-C2 .

revs John Sidles
fuente
No estoy seguro de lo que quieres decir en Q3; parece que la representación de entrada influiría en gran medida exactamente en lo que funcionan las TM.
2
¿Qué es un número real semidefinido positivo? Entiendo "semidefinido positivo" para matrices simétricas reales, pero ¿qué significa para los números?
David Monniaux
Significa cero o mayor (un número visto como una matriz 1x1).
John Sidles
1
Interesante línea de investigación. Durante mucho tiempo pensé que los blums aceleran, pueden tener alguna conexión con preguntas como esta y / o P =? NP, pero no he visto que se haya aclarado o explorado en ninguna parte. en particular, no he visto una prueba muy estricta / rigurosa de que no hay lenguaje en P que también esté en la clase identificada por blum, de modo que el programa "no tenga un algoritmo más rápido"
vzn
1
@JohnSidles No creo que exista ningún lenguaje gnóstico dentro de P, incluso si NP está contenido en P. Quizás podamos separarlos como los que podemos resolver mediante la búsqueda y los otros mediante un método diferente luego de la búsqueda.
Tayfun Pay

Respuestas:

26

Creo que hay una dificultad subyacente fundamental con la pregunta que hace aquí (y que hizo en su pregunta relacionada sobre idiomas incomprensibles).

En términos generales, parece que estás buscando un lenguaje tal queL

pero ZFC no lo sabeLP .LP

Para comprender las dificultades con su pregunta, creo que usted debe primero apreciar que hay una diferencia fundamental entre intensionales y extensionales definiciones de un lenguaje . Extensionalmente, L está determinado por lo que las palabras son o no son miembros de L . Es decir, dos lenguajes L y L ' son extensionalmente iguales si y solo si contienen exactamente las mismas palabras que los miembros. En contraste, una definición intensiva de L describe algunas condicionesLLLLLL para una palabra para estar en . Una máquina de Turing que acepta LLLO una fórmula de primer orden que se cumple si y sólo si x L , puede ser pensado como un intensión de L .ϕ(x)xLL

El punto es que cada que está (extensionalmente) en P admite una descripción que es extremadamente directa, porque P es una clase de complejidad llamada "sintáctica". Es decir, simplemente tome una máquina de Turing con reloj polinómico , que termine exactamente en la cantidad de tiempo deseada. Cualquier sistema "razonable" para hacer matemáticas, como PA o ZFC, podrá demostrar que L PLPPLP si se utiliza esta descripción directa de .L

Así que si desea confundir ZFC, vas a tener que subir con una cierta descripción (intencional) de que está "demasiado complicado" para ZFC reconocer como equivalente a la descripción directa de L . Esto es posible, pero en cierto sentido es demasiado fácil ser interesante. Todo lo que tiene que hacer es tomar algo que sabemos que ZFC no comprende (por ejemplo, su propia consistencia) y mezclarlo con la definición deLL alguna manera. Por ejemplo, aquí hay una descripción de un conjunto de enteros:L

x es par y no codifica una prueba de que ZFC es inconsistente.x

Suponiendo que ZFC es consistente, la fórmula anterior define el conjunto de enteros pares, pero ZFC no lo sabe. Con un poco más pequeños ajustes, podemos obtener fácilmente una descripción del conjunto de enteros pares que ZFC no será capaz de demostrar está en .P

El resultado es que si esperas que la razón por la que es difícil demostrar que es que hay lenguajes en P que son "demasiado complicados" para que podamos razonar, entonces creo que estás ladrando mal árbol. Extensionalmente, cada idioma en P está en P por razones triviales. Puede enturbiar las aguas jugando con descripciones imposiblemente opacas de idiomas en P , pero este es un truco general que no tiene nada que ver con PPNPPPPPP en particular, por lo que no creo que arroje mucha información.

Timothy Chow
fuente
Timothy, gracias por este excelente ensayo. Sin embargo, ¿aprecio correctamente que la definición estándar de P - por complejidad computacional de Arora y Barak : un enfoque moderno y / o computaciones viables de Hartmanis y propiedades de complejidad comprobables , o la declaración del Premio del Milenio - NO es extensional? Sin embargo, quizás algunos problemas serían más manejables si la definición de P se modificara adecuadamente, sobre la base de que (según Hartmanis) "Necesitamos explorar más a fondo cómo debe cambiarse nuestra 'visión del mundo' de la complejidad de los algoritmos si consideramos que solo es demostrable propiedades de los algoritmos ".
John Sidles
2
@JohnSidles la definición estándar de P es "el conjunto de todos los lenguajes que puede decidir un polytime TM". cómo se define un lenguaje (de manera intensiva o extensional) no entra en la imagen en absoluto: solo ingresa en la imagen una vez que necesitamos demostrar que una máquina en particular acepta algún lenguaje en particular.
Sasho Nikolov
1
Sasho, el objetivo de la respuesta de Timothy Chow (como lo leí) es "Si definimos P extensionalmente , entonces decidir membresía en P es trivial". El objetivo de su comentario (tal como lo leí) es que, según la convención actual, " P se define de manera intensiva ". La combinación de estas dos observaciones nos lleva a apreciar el comentario de Hartmanis: "Los resultados sobre la complejidad de los algoritmos cambian radicalmente si consideramos solo las propiedades de los cálculos que pueden probarse formalmente". Y, por lo tanto, naturalmente nos preguntamos cómo se puede variar la definición de P , para demostrar más fácilmente buenos teoremas.
John Sidles
1
PP
Sí, las definiciones de gnóstico y trascendental tienen el propósito de (eventualmente) probar declaraciones como las siguientes: Teorema Sea P ' y NP' las restricciones gnósticas de P y NP resp. Entonces P '≠ NP' . Para una definición adecuadamente amplia pero natural de "gnóstico", tal prueba podría ser comparablemente iluminadora y tener implicaciones prácticas comparables, a una prueba (¿presumiblemente mucho más difícil?) De que P ≠ NP . AFAICT, Juris Hartmanis fue uno de los primeros teóricos de la complejidad en perseguir seriamente esta línea de investigación.
John Sidles
8

Q1: No
Q2: Sí, al menos dos-1-en-binario


Lema: Cada TM con un exponente de tiempo de ejecución computable que es al menos 1 es trascendental.

Prueba:
deje que A y B sean conjuntos recursivamente inseparables .M0M1r0,r1,r2,r3,...M0M1rmmA entonces la afirmación de D1 es verdadera] y [si mB entonces la declaración de D1 es falsa]. r0,r1,r2,r3,...rmPor lo tanto, la máquina de Turing es trascendental.


Definición:
al menos dos 1s en binario es el conjunto de enteros no negativos cuya
representación binaria tiene al menos dos 1s. (Apuesto a que nunca habrías adivinado ^ _ ^)

Definición:
M es la máquina de Turing que escanea la representación binaria de
su entrada, acepta si encuentra al menos dos 1s y rechaza lo contrario.

Obviamente, M decide al menos dos-1-en-binario y tiene exponente de tiempo de ejecución 1, y ninguna otra máquina de Turing con un exponente de tiempo de ejecución más pequeño también decide al menos dos-1-en-binario.
Trivialmente111Por el lema, M es eficiente y trascendental.
Estos significan que al menos dos-1-en-binario también es trascendental.

Por lo tanto, TPCCC es un teorema de PA (y ZFC), y
al menos dos-1-en-binario es un lenguaje trascendental concreto.


fuente
Ricky, muchas gracias! Tomará un par de días contemplar su ingenioso lenguaje "al menos dos-1-en-binario" (ALT1siB) y el TM que lo acepta ... hay consideraciones de naturalidad que son D1-5 (con suerte) sintonizado para garantizar, y que (con suerte) ALT1siB respeta. Se buscan especialmente las intuiciones con respecto a "¿Qué nos enseña ALT1siB sobre la complejidad?" Si desea ofrecer comentarios a este respecto, se lo agradeceríamos con gratitud.
John Sidles
3
(Espero que te des cuenta de esto, pero) Lo único que estoy usando sobre ALT1siB es que tiene una complejidad lineal exacta, por lo que no nos enseña nada sobre la complejidad. Lo que nos enseña el lema es que la mayoría de las máquinas Turing naturales son trascendentales.
r
Hmmm ... para decirlo de otra manera, ya que nuestra definición de trascendental es tan amplia que (según su lema) incluso los TM que (creemos) entienden OK, es decir, los TM que consideramos gnósticos , son de hecho trascendental, entonces la definición de "trascendental" necesita ser (con suerte mínimamente) restringida. Ejemplo: deseamos respetar nuestra intuición de sentido común de que los TM que deciden la primalidad a través de la prueba de primitiva AKS serán gnósticos, no trascendentales. Su respuesta muestra que se necesita un ajuste de definición (con suerte menor) ... pero ¿qué?
John Sidles
1
Ricky, me pregunto si le importaría la edición de su respuesta a dar definiciones explícitas de m , s y t . Tal como están las cosas, las definiciones de estos números tienen que adivinarse, y de ninguna manera estoy seguro de haberlo adivinado correctamente. En particular, ¿entiendo correctamente que cambiar "real" a "racional" en D1 cerraría el vacío que señala su publicación (AFAICT), de modo que bajo el D1 modificado al menos algunas TM son gnósticas?
John Sidles
1

xn:=2+i=0n[1/2i if i encodes a proof that ZF is inconsistent, and 0 otherwise]nxnxnx:=2+i=0[1/2i if i encodes a proof that ZF is inconsistent, and 0 otherwise]

xZF

x>1MxnNsNs|s|x/log(|s|)xMxMxMxMx has runtime O(|s|y) precisely when yx, and that Mx is efficient for its language.

Therefore, for x as in Definition 1, Mx will run in time O(|s|2) precisely if x=2, ie if ZF is consistent; moreover this fact will itself be provable in ZF. So [if ZF is consistent], Mx is a [strongly and canonically] cryptic machine, and this fact will be provable in ZF+Con(ZF).

However, ZF+on(ZF) proves that all languages in P are gnostic, since it proves that ZF proves that every language has runtime O(|s|z) for every z. So it is undecidable in ZF whether any cryptic language exists.

To answer your second and third questions, the definition I gave above for Mx is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.

Ben Standeven
fuente
Ben, thank you for this carefully reasoned and thoughtfully phrased answer. It will take a few days to digest it ... I hope to comment in a week or so!
John Sidles