¿Cuál es el contexto axiomático (teoría de conjuntos) de las conjeturas P vs NP y NP = EXPTIME?

Cuando se establece la conjetura o (por ejemplo, por el Clay Mathematical Institute de S. Cook, ver aquí ) ¿qué sistema axiomático matemático se supone? $\mathbf{P} = \mathbf{NP}$ $\mathbf{P} \neq \mathbf{NP}$

Para probar o refutar tales afirmaciones, debe asumir algunos axiomas. ¿Cuáles? ¿Solo la aritmética de Peano (lenguaje formal de segundo orden)? ¿La teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección? Teorías de conjuntos axiomáticos más pequeños (p. Ej., Conjuntos constructivos de Gödel, donde también se mantiene la hipótesis del continuo, ver aquí ).

Obviamente, debería ser una teoría axiomática que acepte el infinito contable. ¿Pero cuál en particular? ¿Hay algún resultado publicado que demuestre que son consistentes en una teoría de conjuntos axiomática particular? (En otras palabras, definir un modelo en el que es cierto, pero no pretende ser cierto en todos los modelos).

cc.complexity-theory model-theory Constantine Kyritsis
fuente

generalmente se basa en el modelo TM que no ha demostrado tener una dependencia particular en la elección de los axiomas de la teoría de conjuntos ... ¡hasta ahora!

vzn 01 de

D T I M E (n^{α (n)})

$\mathsf{DTIME}(n^{\alpha(n)})$

α (n)

$\alpha(n)$

ver también resultados en TCS independiente de ZFC que indica aproximadamente "no mucho hasta ahora" ...

vzn

Π_{1}^{0}

$\Pi^0_1$

P \neq N P

$P\neq NP$

S A T

$SAT$

Π_{1}^{0}

$\Pi^0_1$ en general .

Damiano Mazza

@DamianoMazza Gracias Damiano, tienes razón, disculpas por hacer un reclamo increíblemente fuerte.

Sasho Nikolov

Respuestas:

No está especificado Cuando haya un documento candidato suficientemente serio que pretenda resolver P ≟ NP, se formará un Comité Asesor Especial para decidir si (y a quién) otorgar el premio. Supongo que el Comité Asesor Especial decidirá si su sistema de axiomas es aceptable. Si asume ZF con opción, le garantizo que lo tomarán. Si asumes P ≠ NP como un axioma, te garantizo que no lo harán.

Peter Shor
fuente

Sería bastante interesante / extraño si se necesita una elección para la prueba (es decir, ZFC funciona, ZF no).

usul

Agradezco a la gente por sus respuestas hasta ahora. Tiene sentido que no se especifique y es variable qué sistema axiomático (teoría de conjuntos) se supone. Me parece que en una teoría de conjuntos axiomática bastante restrictiva (o modelo restrictivo de la teoría de conjuntos axiomática) es más probable que se pueda demostrar que NP = EXPTIME y en un sistema más pluralista (sistema axiomático o modelo de teoría de conjuntos) más probable que NP no es EXPTIME (grados más finos de diferencias de complejidad).

Constantine Kyritsis 01 de

E incluso podría suceder que uno pueda venir con una prueba, que dentro de Peano Aritmética (con conjuntos definibles a partir de fórmulas lógicas solo sin axiomas de la teoría de conjuntos) las famosas conjeturas son independientes y no demostrables (a menos que ya haya un resultado sobre estas conjeturas en el interior Aritmética de Peano o un argumento de imposibilidad más simple que no sé).

Constantine Kyritsis 01 de

Nadie piensa seriamente que P! = NP es independiente de ZFC. No conocemos ninguna declaración matemática no ideada que sea independiente de ZFC (que no sean las obvias de Godelian). Este resultado simplemente no va a suceder.

David Harris

@usul: No es solo extraño, de hecho es imposible. ZFC es conservador sobre ZF para declaraciones aritméticas.

Emil Jeřábek