Qual seria o impacto de P = NP? [fechadas]

18

Estou me preparando para um teste e não consigo encontrar uma resposta clara para a pergunta: qual seria o impacto de provar que PTIME = NPTIME. Eu verifiquei a wikipedia e acabei de mencionar que teria "um impacto profundo em matemática, IA, algoritmos ..." etc.

Alguém pode me dar uma resposta?

algorithms complexity latusaki
fonte
Isso não tem nada a ver com o desenvolvimento de software. Fechei por enquanto, mas perguntei aos mods do Math.StackExchange se eles gostariam que eu migrasse isso para você.
maple_shaft

Respostas:

22

A primeira coisa que vem à mente é que atualmente a segurança da criptografia de chave pública depende da incapacidade de problemas matemáticos de força bruta que estão na classe de dificuldade NP. Se P = NP, tudo o que depende do PKC (incluindo HTTPS, o que significa toda a infraestrutura de comércio eletrônico moderna e mundial ) teria que ser reformulado!

Mason Wheeler
fonte
4
Isso garantiria a existência de algoritmos executados em tempo polinomial. Seria apenas uma contagem regressiva para encontrar esses algoritmos e, em seguida, o kaboom, por assim dizer.
World Engineer
7
Uma prova envolveria encontrar um algoritmo de tempo polinomial para um problema NP-completo. E quando você encontra um algoritmo polinomial, pode usá-lo para resolver todos os outros problemas de NP-completo, reduzindo-os para um formulário comum. Isso significa que uma prova para P = NP e algoritmos que o utilizam aparecerá ao mesmo tempo.
Oleksi
7
É claro que os fatores constantes podem ser tão grandes para tornar isso apenas um problema teórico ... por algum tempo.
Quant_dev 16/05/12
17
Quando encontramos esse algoritmo, ele ainda pode ter um fator constante horrivelmente alto ou um tremendo grau (n ^ 10000 é polinomial, mas, para muitos propósitos práticos, é muito pior que uma pequena complexidade exponencial). É claro que seria um sinal de alerta para todos se afastarem dos métodos antigos, como nos afastamos do DES antes que se provasse ser solucionável, mas a economia mundial não entraria em colapso imediatamente. Basta pensar no próprio dinheiro: todo mundo sabe que ele realmente não funciona, a menos que você acredite nele, mas o comércio global ainda funciona bem.
Kilian Foth
5
Nós provavelmente recorreríamos a usar almofadas únicas. A Amazon poderia enviar para você um pen drive de 1 Gig que funcionaria com o site e o manteria pelo resto da vida.
Macneil 16/05
18

Isso é abordado em O status do problema P Versus NP . Definitivamente vale a pena ler.

Alguns pontos importantes do artigo (citados na seção What If P = NP? ):

  • A criptografia de chave pública se torna impossível.
  • Como todos os problemas de otimização do NP-completo se tornam fáceis, tudo será muito mais eficiente. O transporte de todas as formas será programado de maneira ideal para movimentar pessoas e mercadorias de maneira mais rápida e barata. Os fabricantes podem melhorar sua produção para aumentar a velocidade e criar menos desperdício.
  • O aprendizado se torna fácil usando o princípio do barbeador da Occam - simplesmente encontramos o menor programa consistente com os dados. O reconhecimento quase perfeito da visão, a compreensão e tradução de idiomas e todas as outras tarefas de aprendizado tornam-se triviais. Também teremos previsões muito melhores de clima, terremotos e outros fenômenos naturais.
  • P = NP também teria grandes implicações em matemática. Pode-se encontrar provas curtas e totalmente lógicas para os teoremas, mas essas provas são geralmente extremamente longas. Mas podemos usar o princípio da navalha Occam para reconhecer e verificar provas matemáticas, como normalmente escrito em periódicos. Podemos então encontrar provas de teoremas com provas de comprimento razoável, digamos em menos de 100 páginas. Uma pessoa que provar P = NP voltaria para casa do Clay Institute não com um cheque de US $ 1 milhão, mas com sete (na verdade seis desde que a Conjectura de Poincaré parece resolvida).
vinaykola
fonte
2
Não vejo como P = NP implica que a criptografia de chave pública é impossível. Ele sugere (mas não implica) que as implementações atuais não sejam tão difíceis de quebrar quanto pensávamos anteriormente. Mas, como outros já apontaram, se as constantes relevantes em um algoritmo de redução de tempo ideal forem extremamente grandes, P = NP não teria nenhum impacto na criptografia de chave pública.
Emory
+1 para o terceiro ponto - todo mundo sabe que P = NP afetaria a criptografia, mas por algum motivo você raramente ouve sobre como isso afetaria literalmente todas as outras disciplinas de computação do planeta.
BlueRaja - Danny Pflughoeft
@emory: não pretendo ser um especialista, mas meu entendimento é que, se um algoritmo desse tipo fosse encontrado, mesmo com uma constante bastante alta, teríamos que repensar totalmente nossa abordagem. Além disso, quem pode dizer que, depois que um algoritmo é encontrado, não podemos encontrar outro com uma constante menor? Um algoritmo também desbloquearia todos os outros problemas de NP-completo. Portanto, o efeito imediato pode não ser grande, mas seria necessário pensar bastante na alteração de todos os sistemas existentes.
Vinaykola
primeira vez que ouvi falar do princípio da navalha de Occam. Coisas interessantes ...
UmNyobe 16/05
@vinaykola provar que P = NP não implica encontrar um algoritmo. É claro que encontrar um algoritmo seria a maneira mais direta (mas não a única) de provar P = NP e, se as constantes fossem razoáveis, poderíamos entrar nas questões que você levantou.
Emory
7

A maioria dos problemas completos do NP possui aplicativos "interessantes" da vida real. P=NPterá muitas consequências:

  • Será possível resolver exatamente os problemas de otimização atualmente aproximados. É o caso do problema do vendedor ambulante e do problema de agendamento de tarefas
  • Ele quebra algumas medidas de segurança baseadas no fato de que o tempo computacional necessário é enorme. Por exemplo, muitos esquemas de criptografia e algoritmos em criptografia são baseados na fatoração de números, o algoritmo mais conhecido com complexidade exponencial. Esses algoritmos se tornarão inúteis se um algoritmo polinomial for encontrado.

A linha inferior é sobre a natureza dos problemas conhecidos por serem NP-completos. Estes não são apenas problemas criados por poucos cientistas em um local remoto para se divertir. Eles podem ser expressos em termos de negócios. De fato, alguns entrevistadores gostam de esconder problemas completos de NP em suas perguntas para testar os candidatos.

UmNyobe
fonte
3
Embora a fatoração inteira seja um problema difícil, vale a pena notar que ela não é conhecida como NP-completa.
Dan_waterworth 16/05/12
4
@dan_waterworth: Não se sabe se a fatoração inteira é NP-difícil, mas sabe-se que está em NP. [Muitas vezes, parece que as pessoas dizem "NP-complete" quando significam "in NP" ou "NP-hard". De certa forma, seria como alguém dizendo "menor ou igual a" em uma situação onde "menos do que" seria mais preciso].
Macneil
5

Essas possibilidades são abordadas nos Cinco Mundos de Impagliazzo .

Aqui estão alguns pontos de referência:

  • A inteligência artificial seria capaz de dar um salto gigante. Por exemplo, com "dados de treinamento" suficientes, os curtos-circuitos para produzir as saídas corretas das entradas representariam o melhor método de tradução. Em particular, seria trivial ter um perfeito reconhecimento de fala e tradução de idiomas. Levando essa idéia adiante, se seus dados de treinamento forem filmes vencedores do Oscar, eles poderão gerar mais filmes premiados para você.

  • Os algoritmos ensinados nas escolas seriam radicalmente diferentes. Em vez de aprender tantas técnicas algorítmicas diferentes , os cursos se concentrariam em reduzir problemas à verificação de respostas corretas. Isso simplificaria bastante a programação.

  • A economia se tornaria muito mais eficiente. Haveria interrupção, incluindo talvez o deslocamento de programadores. A prática da programação em si seria mais sobre reunir dados de treinamento e menos sobre escrever código. O Google teria os recursos para se destacar em um mundo assim.

  • Como a criptografia de chave pública ficaria "fora", a Amazon precisaria enviar um bloco único em um pen drive para realizar transações seguras.

  • Provas matemáticas podem ser geradas e verificadas automaticamente.

Globalmente, introduziria uma singularidade tecnológica; as implicações de P = NP seriam de grande alcance. Além disso, Lance Fortnow aborda esse ponto em uma postagem de blog separada que você deve ler.

Macneil
fonte
-1

O impacto de provar P = NP incluiria um interesse renovado em encontrar um algoritmo de redução. As pessoas também tentariam encontrar alguns limites inferiores nas constantes associadas ao algoritmo de redução.

Provar P = NP não seria tão significativo quanto as outras respostas afirmam, pois poderia vir na forma de uma prova de conhecimento zero. Conhecer P = NP sem conhecer o algoritmo de redução seria um pouco diferente da situação atual.

Imagine se alguém provasse que o algoritmo de redução existia, mas é O (sqrt (n) + 2 ^ 4096).

emory
fonte
1
Na verdade, existe um algoritmo de redução explícito que está em P se e somente se P = NP. Consiste em iterar sobre todos os programas possíveis e executá-los em paralelo até encontrar a solução.
Arthur B
@ArthurB fascinante. Supondo que P = NP, qual é a ordem do algoritmo?
Emory
É desconhecido, mas é a ordem ideal. scholarpedia.org/article/Universal_search
Arthur B
1
@ ArthurB então se P = NP e o algoritmo de redução é O (n ^ 99999999) P = NP ainda é um problema?
Emory