Qual é o contexto axiomático (teoria dos conjuntos) das conjecturas P vs NP e NP = EXPTIME?

Quando a conjectura ou é definida (por exemplo, pelo Clay Mathematics Institute de S. Cook, veja aqui ) que sistema axiomático matemático é assumido? $\mathbf{P} = \mathbf{NP}$ $\mathbf{P} \neq \mathbf{NP}$

Para provar ou refutar tais declarações, você precisa assumir alguns axiomas. Quais? Apenas a aritmética Peano (linguagem formal de 2ª ordem)? A teoria de Zermelo-Fraenkel define o axioma da escolha? Teorias axiomáticas menores de conjuntos (por exemplo, conjuntos construtíveis de Gödel, onde a hipótese do continuum também se aplica, veja aqui )?

Obviamente, deveria ser uma teoria axiomática que aceita o infinito contável. Mas qual em particular? Existe algum resultado publicado que os prove ser consistente em uma teoria axiomática específica dos conjuntos? (Em outras palavras, definir um modelo em que seja verdadeiro, mas não afirmando ser verdadeiro em todos os modelos).

cc.complexity-theory model-theory Constantine Kyritsis
fonte

geralmente é baseado no modelo de TM que não demonstrou ter nenhuma dependência em particular da escolha dos axiomas da teoria dos conjuntos ... até agora!

vzn

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

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

α (n)

$\alpha(n)$

ver também resulta em TCS independente de ZFC que indica aproximadamente "não muito até agora" ...

vzn

Π_{1}^{0}

$\Pi^0_1$

P \neq N P

$P\neq NP$

S A T

$SAT$

Π_{1}^{0}

$\Pi^0_1$ em geral .

Damiano Mazza

@DamianoMazza Obrigado Damiano, você está certo, desculpas por fazer uma afirmação incrivelmente forte.

Sasho Nikolov

Respostas:

Não está especificado. Quando houver um trabalho candidato suficientemente sério para resolver a P ≟ NP, um Comitê Consultivo Especial será formado para decidir se (e a quem) será concedido o prêmio. Presumo que o Comitê Consultivo Especial decidirá se seu sistema de axiomas é aceitável. Se você assumir a ZF com escolha, garanto que eles a aceitarão. Se você assumir P ≠ NP como um axioma, garanto que não.

Peter Shor
fonte

Seria bastante interessante / bizarro se a escolha fosse necessária para a prova (por exemplo, o ZFC funciona, o ZF não).

usul

Agradeço ao povo por suas respostas até agora. Faz sentido que não seja especificado e é variável qual sistema axiomático (teoria dos conjuntos) é assumido. Parece-me que, em uma teoria axiomática dos conjuntos bastante restritiva (ou modelo restritivo da teoria axiomática dos conjuntos), é mais provável que se possa provar que NP = EXPTIME e em um mais pluralista (sistema axiomático ou modelo da teoria dos conjuntos) mais provável que NP não é EXPTIME (graus mais finos de diferenças de complexidade).

Constantine Kyritsis

E pode acontecer que se prove uma prova de que, dentro da Aritmética Peano (com conjuntos definíveis a partir de fórmulas lógicas apenas sem axiomas da teoria dos conjuntos), as famosas conjecturas são independentes e não prováveis (a menos que já exista um resultado nessas conjecturas) Aritmética Peano ou um argumento de impossibilidade mais simples que eu não conheço).

Constantine Kyritsis

Ninguém pensa seriamente que P! = NP é independente do ZFC. Não conhecemos nenhuma declaração matemática não inventada que seja independente da ZFC (além das óbvias Godelianas). Este resultado simplesmente não vai acontecer.

David Harris

@usul: Não é apenas bizarro, é de fato impossível. O ZFC é conservador em relação ao ZF para declarações aritméticas.

Emil Jerabek