Reduzindo P vs. NP para SAT

12

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?

MS Dousti
fonte
Não entendi esta parte: "Vamos σ denotar a prova. Então, P vs. NP está em NP (já que existe uma prova curta). A redução do teorema (digamos, P ≠ NP) para o NP -complete problem (digamos SAT) é independente de σ. Ou seja: Existe uma fórmula ϕ que é satisfatória se e somente se P ≠ NP. ". Poderia explicar um pouco mais? Não faz sentido para mim que "P vs NP esteja em NP", mesmo que você mude para "existe uma prova de comprimento no máximo n na teoria T para P \ neq NP". Ou existe um menor n, existe uma prova desse tamanho para a pergunta ou não existe essa prova.
Kaveh
1
φnφTφ
φPNPT
@ Kaveh: Esclarecimento adicionado.
MS Dousti 17/10/10
algumas idéias interessantes, mas não faz sentido dizer que uma "prova está em NP" ou que "existe uma prova curta". ou seja, poderia haver algum método para fazer esses paralelos, mas teria que ser definido formalmente. o mais próximo dessas idéias, ao que parece, seria o quadro de provas naturais razborov / rudich.
fácil

Respostas:

20

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!

Dana Moshkovitz
fonte
9

P vs. NP está em NP (já que existe uma pequena prova disso)

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:

seja L uma linguagem NP na qual P vs. NP esteja.

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 retorne false.

Alexey Romanov
fonte
2
Por favor, leia a nota lateral no início da pergunta novamente. Eu estava colocando isso informalmente, e isso leva à sua confusão. Para formalizar, é preciso considerar uma generalização do teorema "P vs. NP". Para infinitamente muitos n, a generalização assume um teorema de comprimento n. Os teoremas dão origem a uma linguagem L, que não pode ser decidida em DTIME (1).
MS Dousti 17/10/10
Então, uma prova curta / desaprovação de "P vs. NP" é apenas uma instância de "P vs. NP generalizado" (talvez uma tarefa fácil?), E não se segue que o GPvNP esteja em NP.
Alexey Romanov
Voto negativo: Entendo a objeção à forma como a primeira declaração citada é redigida, uma vez que os membros do NP são conjuntos e "P vs. NP" não é um conjunto. No entanto, na segunda objeção, qualquer "problema de PN" é um problema de decisão que sempre pode ser legitimamente formulado para decidir se uma string está em um idioma; Não vejo nada de errado com sua definição de L. Além disso, o apelo a linguagens triviais, sempre verdadeiras ou sempre falsas DTIME (1) ignora o ponto: se já conhecemos TODAS as afirmações verdadeiras, presumivelmente criamos uma aparência. tabela para a máquina de Turing acessar a tempo constante.
Daniel Apon 17/10/10
[Continua] Mas, assumindo que L é uma linguagem adequada (ou seja, um conjunto infinito), você está assumindo uma tabela infinitamente grande de "declarações verdadeiras" para acessar, o que parece quebrar todos os tipos de regras. Ou, mais precisamente: por que seu argumento para DTIME (1) não generaliza para QUALQUER idioma, não apenas para o estranho que estamos considerando agora?
Daniel Apon 17/10/10
1
LDTIME(1)