Como não resolver P = NP?

96

Existem muitas tentativas de provar ou PN P , e naturalmente muitas pessoas pensam sobre a questão, tendo idéias para provar qualquer direção.P=NPPNP

Eu sei que existem abordagens que comprovadamente não funcionam, e provavelmente há outras que têm um histórico de falhas. Também parece haver barreiras que muitas tentativas de prova não conseguem superar.

Queremos evitar investigar os becos sem saída, então o que são?

Rafael
fonte
16
Eu acho que é melhor ser um wiki da comunidade (porque não há uma resposta única para essa pergunta, é muito ampla).
6
@SaeedAmiri Não. O wiki da comunidade costumava ser um álibi para permitir perguntas que não eram adequadas para a plataforma Stack Exchange, mas isso não é mais feito .
Gilles
4
Nota do moderador: essa pergunta é mais ampla que uma pergunta normal do Stack Exchange, mas estamos tentando criar uma pergunta canônica e um par de respostas. Se você acha que essa pergunta não deveria existir em sua forma atual, discuta-a em nosso meta site .
Gilles
para uma pergunta semelhante do lado oposto / construtivo, veja como as teorias e investigações de ciência da computação podem ser resolvidas?
vzn
4
Wag resposta: arXiv é um tesouro de maneiras de não fazê-lo.
Pseudônimo

Respostas:

76

P=NP

  1. Relativização (como mencionado por Ran G.)
  2. PNP
  3. PNP

Outro que eu conheço é o resultado de que nenhuma formulação de LP pode resolver o TSP (foi provado por Yannakakis para LPs simétricos e muito recentemente estendido para LPs gerais). Aqui está uma postagem no blog discutindo o resultado.

Optar
fonte
4
PNPP
1
Se você quiser melhorar a resposta (ela ainda não está pronta para aceitação), adicione breves explicações e links para detalhes para que o leitor curioso saiba do que está falando.
Raphael
57

Nota: Ainda não verifiquei a resposta com cuidado e faltam partes a serem escritas, considere-a um primeiro rascunho.

Essa resposta é direcionada principalmente para pessoas que não são pesquisadores da teoria da complexidade ou de campos relacionados. Se você é um teórico da complexidade e leu a resposta, entre em contato se notar algum problema ou tiver alguma idéia para melhorar a resposta.

Onde você pode encontrar soluções reivindicadas de P vs. NP

  • Há a página P-versus-NP, que possui uma lista de tais reivindicações.
  • Os artigos que alegam resolver a questão são publicados regularmente no arXiv .

Outras listas de como não resolver P vs. NP

Lance Fortnow, então você pensa que se estabeleceu P verus NP , 2009

Scott Aaronson, Oito sinais de que uma prova de P ≠ NP está errada , 2010

Página Polymath para o artigo de Deolalikar , onde a seção de leituras adicionais possui uma boa lista de referências sobre o problema.


Como não abordar P vs. NP

Deixe-me discutir "como não abordar P vs. NP" não no sentido de idéias que não funcionarão, mas em um sentido mais geral. P vs. NP é um problema fácil de declarar (veja também minha resposta aqui ):

NP = P: Para todo problema de decisão com um algoritmo de verificação de tempo polinomial, existe um algoritmo de tempo polinomial.

ou equivalente

Existe um algoritmo de tempo polinomial para SAT.
O SAT pode ser substituído por qualquer outro problema NP-completo .

.

Muitas vezes, as pessoas simplificam demais e exageram a filosofia e exageram a importância prática do problema (como afirmado acima). Tais declarações costumam dar intuição, mas não substituem de maneira alguma a declaração matemática real do problema.

Eficiência teórica não é o mesmo que viabilidade na prática.

Deixe-me primeiro com consequências práticas exageradas.

I. É possível que P = NP, mas não ajude por nenhum problema na prática!

2264n65536+22128

nlglgn

lgn>62

O ponto principal aqui é que P é um modelo simples abstrato de computação eficiente, a complexidade do pior caso é um modelo simples abstrato de estimativa do custo de uma computação etc. Tudo isso são abstrações, mas ninguém na prática consideraria um algoritmo como o descrito em (I) acima como um algoritmo eficiente, na verdade. P é um bom modelo abstrato, possui boas propriedades, facilita as questões técnicas e é útil. No entanto, como toda abstração matemática, oculta detalhes com os quais, na prática, podemos nos importar. Existem vários modelos mais refinados, mas quanto mais complicado o modelo se torna, menos agradável seria discutir.

O que as pessoas se preocupam na prática é calcular uma resposta para o problema nos casos em que se preocupam em usar uma quantidade razoável de recursos. Existem tarefas dependentes e devem ser levadas em consideração.

Tentar encontrar melhores algoritmos para instâncias práticas de problemas difíceis de NP é um esforço interessante e digno. Existem algoritmos heurísticos do SAT-solver que são usados ​​na indústria e podem resolver instâncias práticas do SAT com milhões de variáveis. Existe até uma competição internacional SAT .

(Mas também existem pequenas instâncias concretas em que todos esses algoritmos falham e falham bastante, podemos realmente provar que todos os solucionadores modernos de SAT de última geração levam tempo exponencial para resolver instâncias simples como o Princípio Pigeonhole proposicional .)

Lembre-se de que a correção e o tempo de execução dos programas não podem ser obtidos apenas com a execução do programa nas instâncias . Não importa quantas instâncias você tente, nenhuma quantidade é suficiente. Existem inúmeras entradas possíveis e você precisa mostrar correção e eficiência (ou seja, o tempo de execução é polinomial) do programa para todas elas. Em resumo, você precisa de provas matemáticas de correção e eficiência. Se você não sabe o que é uma prova matemática, deve primeiro aprender matemática básica (leia um livro didático de matemática / combinatória / teoria de gráficos, este é um bom tópico para aprender sobre o que é considerado uma prova matemática).

Também tenha cuidado com outras afirmações sobre P vs. NP e a conseqüência de suas respostas. Tais alegações são frequentemente baseadas em simplificações semelhantes.

Os teóricos da complexidade realmente não se preocupam com uma resposta para P vs. NP!

Eu exagerei um pouco. É claro que nos preocupamos com uma resposta para P vs. NP. Mas nos preocupamos com isso em um contexto. P vs. NP é o nosso principal problema, mas não é o objetivo final. É um problema fácil de declarar, envolve muitas idéias fundamentais, é útil para explicar o tipo de perguntas em que estamos interessados ​​para pessoas que não estão familiarizadas com o tópico. Mas não buscamos uma resposta Sim / Não para a pergunta.

Buscamos uma melhor compreensão da natureza da computação eficiente . Acreditamos que resolver a questão virá com esse entendimento e essa é a verdadeira razão pela qual nos preocupamos. Faz parte de um enorme corpo de pesquisa. Se você quiser provar o que fazemos, consulte um bom livro de teoria da complexidade, por exemplo, " Teoria da complexidade: uma abordagem moderna " , de Arora e Barak ( versão preliminar ).

Em resumo, da perspectiva de um teórico da complexidade

P vs. NP não é um quebra-cabeça com resposta Sim / Não. Buscamos uma resposta para P vs. NP porque achamos que ele compreenderá melhor a natureza da computação eficiente. Uma resposta sem um grande avanço em nosso entendimento não é muito interessante.

Houve muitas ocasiões em que não especialistas reivindicaram soluções para P vs. NP, e essas alegações geralmente sofrem com problemas que não teriam sido feitos se acabassem de ler um livro padrão sobre teoria da complexidade.

Problemas comuns P = NP

As reivindicações de P = NP parecem ser mais comuns. Eu acho que o seguinte é o tipo mais comum. Alguém tem uma idéia e escreve um programa e o testa em algumas instâncias, pensa que é hora polinomial e resolve corretamente um problema completo de NP. Como expliquei acima, nenhuma quantidade de testes mostrará P = NP. P = NP precisa de uma prova matemática , não apenas de um programa que parece resolver um problema de NP completo em tempo polinomial.

Essas tentativas geralmente sofrem de um dos dois problemas:

I. o algoritmo não é realmente um tempo polinomial.

II o algoritmo não resolve todas as instâncias corretamente.

[a ser escrito]

Como verificar se seu algoritmo realmente não funciona

Você não pode mostrar que seu algoritmo funciona corretamente testando. Mas você pode mostrar que não funciona corretamente testando! Então, aqui está como você pode garantir que seu algoritmo não esteja correto se você estiver disposto a fazer algum trabalho.

Primeiro, escreva um programa para converter instâncias do SAT (no formato CNF padrão) no problema difícil de NP que você está solucionando. O SAT é um dos problemas mais difíceis de NP estudados e a redução de outros problemas para o SAT é geralmente fácil. Segundo, pegue os exemplos com os quais os solucionadores de SAT de ponta enfrentam (por exemplo, pegue os exemplos da competição por SAT) e alimente-os com seu algoritmo e veja como ele funciona. Experimente instâncias concretas conhecidas como o Princípio Pigeonhole proposicional (e não trapaceie codificando-as como casos especiais), instâncias criptográficas (como RSA Factoring Challenges ), instâncias aleatórias de k-SAT próximas ao limite etc.

10n2

Como verificar sua ideia algorítmica P = NP não pode funcionar

Se você fizer isso, terá certeza de que seu algoritmo não funciona (se funcionar melhor do que os solucionadores SAT de última geração, concorra na próxima competição e muitas pessoas estariam interessadas em estudar seu algoritmo e suas idéias).

Agora você sabe que realmente não funciona, mas isso não é suficiente. Você quer saber por quê,

é a razão pela qual meu algoritmo não funciona em um pequeno problema que pode ser corrigido ou há uma razão fundamental para que ele não funcione?

Às vezes, o problema com o algoritmo é simples e é possível identificar o que estava errado conceitualmente. O melhor resultado é que você entende o motivo pelo qual sua ideia não pode funcionar. Freqüentemente não é o caso, sua ideia não funciona, mas você não consegue descobrir o porquê. Nesse caso, lembre-se:

entender por que alguma idéia não pode funcionar pode ser mais difícil do que resolver P vs. NP!

Se você puder formalizar sua ideia o suficiente, poderá provar as limitações de idéias específicas (por exemplo, existem resultados que dizem que formalizações específicas do algoritmo ganancioso não podem resolver problemas completos de NP). No entanto, é ainda mais difícil e você não tem muita chance se não leu um livro de teoria da complexidade padrão.

Em algum momento, nem sequer existe uma idéia conceitual clara do motivo pelo qual o algoritmo deve funcionar, ou seja, é baseado em algumas heurísticas não bem compreendidas . Se você não tem uma idéia conceitual clara de por que seu algoritmo deve funcionar, talvez não tenha muita chance de entender por que ele não funciona!

Questão 1: o autor não conhece a definição de P e NP, ou pior ainda, não entende o que é uma prova matemática. Como o autor não possui treinamento matemático básico, ele não entende quando lhe dizem que o que ele está apresentando não é uma prova (por exemplo, as etapas não seguem as anteriores).

Questão 2: o autor confunde "não sabemos como" com "impossibilidade matemática". Por exemplo, eles fazem várias suposições injustificadas e, quando perguntados "por que essa afirmação é verdadeira?" eles respondem "como isso pode ser falso?". Um comum é supor que qualquer programa que resolva o problema precise executar etapas específicas, por exemplo, ele deve calcular valores intermediários específicos, porque ele não consegue pensar em uma maneira alternativa de resolver o problema.

[a ser concluído]

[a ser escrito]

Se uma reclamação não sofrer desses problemas básicos, rejeitá-la se tornará mais difícil. No primeiro nível, pode-se encontrar uma etapa incorreta no argumento. A resposta típica do autor é que eu posso consertar e isso pode continuar. Semelhante às soluções P = NP, muitas vezes é muito difícil encontrar um problema fundamental com uma ideia que possa mostrar que ela não funciona, principalmente quando a ideia em si é informal.

Kaveh
fonte
Por mais que eu goste da página P-versus-NP, acho irritante que ele não acompanhe quais provas foram retiradas por seus autores. Para alguns dos links do arXiv, você encontra avisos explícitos "este documento foi retirado" no arXiv. Tenho certeza de que existem mais provas retiradas do que apenas os documentos do arXiv com aviso explícito. OK, estou ciente de que as provas retiradas não devem ser exageradas, porque a retirada de uma "tentativa anterior de prova" não implica que os mesmos autores não tentem novamente mais tarde. Mas manter silêncio sobre tentativas de retirada de provas ainda dá uma impressão tendenciosa.
Thomas Klimpel
@thomas poucos dos autores "malucos" já "retiram" seus trabalhos. o ponto tácito da lista de woegorgi é que sua qualidade é nitidamente menor que os documentos arxiv. mas, concordou, gostaria que woegorgi adicionasse algumas informações adicionais e que houvesse um pouco mais de flexibilidade em sua edição. por exemplo, ele não colocou meu esboço P vs NP na lista mesmo depois de enviá-lo por e-mail, embora recentemente ele tenha postado outro item na prova de fukuyama relacionada a um longo bate-papo sobre cstheory.se.
vzn
1
Agradeço que você esteja revisitando isso! Parece que eu prematuramente concedi a recompensa à pessoa errada, afinal. ;) Observe que você pode usar o stackedit.io para preparar uma postagem com o tempo. Ansioso para o resto do post!
Raphael
34

Talvez a técnica mais comum que não possa ser usada seja a relativização , ou seja, ter uma MT com acesso ao oráculo.

ABPA=NPAPBNPB

PNPOPONPOA

P=?NP

Tocou.
fonte
1
Para corrigir completamente, aqui diagonalização significa diagonalização simples direta . Veja esta pergunta
Kaveh
1
Então a relativização não é a técnica da prova, mas o efeito que quebra uma prova? Você pode dar / vincular a um exemplo de prova que pode ser relativizada?
Raphael
2
sim, a relativização não é uma técnica de prova, é uma propriedade de uma prova (não sendo formal aqui entre). se a prova funcionar inalterada quando todas as máquinas de turing são substituídas por máquinas oracle, a prova é relativizada. você pode se convencer de que a prova do teorema da hierarquia do tempo é relativizada nesse sentido, por exemplo.
Sasho Nikolov 04/08/2012
10

Eu sugiro ler este post de Lance Fortnow no blog :

  1. Então você pensa que se estabeleceu P verus NP Você está errado. Entender. Às vezes, você ainda pode recuperar algo interessante de sua prova defeituosa.
  2. Você acredita que a prova está correta. Sua crença está incorreta. Volte para a etapa 1.
  3. Você está fazendo suposições ou atalhos, mesmo os aparentemente pequenos e óbvios? Você está usando palavras como "claramente", "obviamente", "fácil de ver", "deveria", "deve" ou "provavelmente"? Você está reivindicando resolver talvez a questão mais importante de toda a matemática. Você não pode fazer suposições. Volte para a etapa 1.
  4. nk
  5. Você envia seu artigo para um arquivo on-line. Talvez algumas pessoas lhe digam o que está faltando ou errado no seu trabalho. Isso deve fazer com que você vá para a etapa 1. Mas, em vez disso, faça algumas alterações sem sentido no seu artigo e republique.
  6. Eventualmente, as pessoas ignoram o seu papel. Você se pergunta por que não está recebendo fama e fortuna.
  7. Você envia seu artigo para um diário.
  8. O artigo é rejeitado. Se você for esperto, voltará ao passo 1. Mas se você fosse esperto, nunca teria chegado ao passo 7.
  9. Você reclama ao editor que o editor não entende a prova ou que é facilmente corrigido. Você está chocado que um editor ou periódico respeitável trataria seu trabalho dessa maneira.
  10. Você reenvia o artigo, apela, tenta outros periódicos, todos sem sucesso.
  11. Você está convencido de que "o estabelecimento" está propositadamente suprimindo seu trabalho, porque nosso campo ficaria muito menos interessante se resolvermos o problema P versus NP, para que tenhamos de mantê-lo aberto a todo custo.
  12. Se eu disser o contrário, você acreditaria em mim?
Kaveh
fonte
7
A pergunta pede “abordagens que comprovadamente não funcionam” e abordagens “que têm histórico de falhas”, e essa resposta não menciona nenhuma abordagem.
Tsuyoshi Ito
6
O que quero dizer é que, como a postagem do blog não responde à pergunta, não faz sentido copiá-la e colar.
Tsuyoshi Ito
7
Isso realmente não responde à pergunta. A postagem do blog é uma lista sarcástica de etapas que o típico P = NP? manivela passa. Embora divertido, isso não me fornece teorias específicas que demonstraram ser incapazes de separar (ou colapsar) P e NP.
Raphael
4
Que tal agora? Esta pergunta pede barreiras para provar P! = NP. As barreiras nesta resposta (como declaradas nos comentários) estão "assumindo algo", "má interpretação", "dizendo que algo está claro", "acreditando em algo". Essas barreiras são muito gerais porque são barreiras para provar qualquer coisa e não especificamente barreiras para provar P! = NP.
Tyson Williams
1
todos os comentários válidos estão sem um ponto básico. o blog foi escrito por lance fortnow, um especialista em complexidade e autoridade mundial sobre o assunto; ele acabou de lançar um novo livro sobre P vs NP Golden Ticket . então ele fala basicamente por experiência pessoal.
vzn
2

aqui está um ângulo / referência / distorção um tanto obscuro / profundo / difícil / privilegiado relacionado a abordagens via circuitos datados da década de 1980, originalmente apontado para mim anos atrás por Luca Trevisan em outros lugares do ciberespaço, e também reiterado por Stasys Jukna, autor de um excelente referência próxima ao assunto, Complexidade da função booleana: avanços e fronteiras (Algorithms and Combinatorics, Vol. 27 ).

pode-se ver uma tendência anterior em alguns dos pensamentos de Razborov que eventualmente levaram ao artigo de Provas Naturais (a chamada "naturalização"). ref [273] é muito técnico e difícil e não parece ser citado, construído / expandido ou reiterado por artigos / livros posteriores, embora as Provas Naturais possam ser vistas como uma grande generalização posterior. o trecho é de John E Savages excelente ref Models of Computation p457

Ω(n2)n

[270] AA Razborov, "Limites inferiores na complexidade monótona de algumas funções booleanas", Dokl. Akad. Nauk SSSR (Soviet Soviet. Dokl.) 281 (1985), 798-801 (em russo); Tradução para o inglês na matemática soviética. Dokl. 31 (1985), 354-357

[271] AA Razborov, “Um limite inferior da complexidade monótona da rede da permanente lógica”, Mat. Zametki 37 (1985), 887–900 (em russo); Tradução para o inglês em matemática. Notas 37 (6) (1985), 485–493.

[273] AA Razborov, "Sobre o método de aproximações", Proc. 21st Ann. ACM Symp. Teoria da computação (1989), 167-176.

vzn
fonte
2
Não vejo como isso responde à pergunta "como não provar P? = NP". No momento, parece mais algum tipo de especulação sobre os pensamentos de alguém.
Juho6
2
Claro, estou apenas sugerindo tornar tudo isso explícito. A complexidade do circuito nem sequer é material de nível de graduação, portanto, alguns antecedentes são justificados. É justo esperar que o leitor não seja um especialista em teoria da complexidade.
Juho 06/06
@juho ok. uma vez que vi o livro Savage [que é muito "centrado em circuito"] usado em uma classe de graduação, ele também me surpreendeu. concordou com seu material avançado, daí a redação da 1ª frase. quanto à "especulação sobre pensamentos", não há, exceto citando os próprios pensamentos de Razborov como escritos / registrados em seus próprios trabalhos.
vzn
1
e, a propósito, em geral, essa é uma pergunta muito avançada (não na verdade, nível de graduação) e outras respostas são avançadas e geralmente fora do nível de graduação.
vzn