A pergunta a seguir usa idéias da criptografia aplicada à teoria da complexidade. Dito isso, é uma questão puramente teórica da complexidade e nenhum conhecimento criptográfico é necessário para respondê-lo.
Eu deliberadamente escrevo essa pergunta de maneira muito informal. Na falta de detalhes, é possível afirmar um pouco incorretamente. Sinta-se à vontade para apontar as correções nas suas respostas.
No seguinte documento:
Nonmalleable Cryptography, Danny Dolev, Cynthia Dwork e Moni Naor, SIAM Rev. 45, 727 (2003), DOI: 10.1137 / S0036144503429856 , escrevem
os autores:
Suponha que o pesquisador A tenha obtido uma prova de que P ≠ NP e deseje comunicar esse fato ao professor B. Suponha que, para se proteger, A prove sua afirmação de B de maneira que não conheça ...
Existem vários problemas padrão de NP completo, como satisfação (SAT), Hamiltonicidade do gráfico e Colorabilidade do gráfico 3 (G3C), para os quais existem provas de zero conhecimento. A maneira padrão de provar qualquer teorema de NP é primeiro reduzi-lo a uma instância dos problemas de NP completos acima mencionados e, em seguida, realizar a prova de zero conhecimento.
Esta questão refere-se a essa redução. Suponha que P vs. NP seja liquidado de uma das seguintes maneiras:
- P = NP
- P ≠ NP
- P vs. NP é independente da teoria axiomática padrão dos conjuntos.
Deixe σ denotar a prova. Então, P vs. NP está em uma linguagem NP (já que existe uma pequena prova disso). A redução do teorema (digamos, P ≠ NP) para o problema NP-completo (digamos SAT) é independente de σ. Isso é:
There exists a formula ϕ which is satisfiable if and only if P ≠ NP.
Isso está muito além da minha imaginação! Parece que, mesmo se nos for dada a prova σ, é improvável que possamos construir essa fórmula ϕ.
Alguém poderia lançar alguma luz sobre isso?
Além disso, seja L uma linguagem NP na qual P vs. NP esteja. A linguagem consiste em infinitos teoremas como P vs. NP , de tamanhos arbitrários.
O que é um candidato para L?
L pode ser NP-completo?
Respostas:
A maneira de visualizar o teste de uma instrução matemática (por exemplo, uma resolução de P vs NP) como uma questão do formato "é a fórmula .. satisfatória" é a seguinte:
Corrija algum sistema de axioma. Dada uma sequência de comprimento n, se a sequência é uma prova da afirmação matemática no sistema axioma, é algo que se pode definir de maneira direta: a sequência deve consistir em proposições. Cada proposição deve ser um axioma ou deve seguir as proposições anteriores por uma das regras de inferência.
Não é um problema definir uma fórmula booleana que verifique tudo isso. Tudo o que você deve saber é o comprimento n da prova!
fonte
Isso não faz muito sentido para mim. NP é uma classe de complexidade para problemas de decisão que possuem instâncias arbitrariamente grandes e P vs. NP não os possui. Pelo que você diz mais tarde:
em vez disso, você pode dizer que P vs. NP é uma instância de um problema de NP; mas é claro que é! Também é instância de um número infinito de problemas de P, DTIME (n) etc. Em particular, aqui estão dois candidatos DTIME (1) para L, precisamente um dos quais está correto: sempre retorne
true; ou sempre retornefalse.fonte