Quais seriam as implicações do mundo real de uma prova construtiva de

Eu tenho um entendimento de alto nível do problema e entendo que, se fosse absolutamente "comprovado" ser verdadeiro com uma solução fornecida, isso abriria a porta para a solução de vários problemas no campo da ciência da computação.$P=NP$

Minha pergunta é: se alguém publicasse uma prova construtiva e indiscutível de , quais são alguns dos efeitos imediatos que veríamos dessa descoberta? $P=NP$

Não estou pedindo opiniões opinativas sobre como o mundo seria em 5 a 10 anos. Em vez disso, entendo que esse é um problema fundamentalmente insolúvel que pode mudar radicalmente a maneira como computamos ... muitas coisas (sim, é aqui que minha ignorância está mostrando ...) que não podemos calcular facilmente hoje .

Que tipo de efeito quase imediato teria uma prova completa, precisa e construtiva de no mundo prático?$P=NP$

As pessoas deram boas respostas assumindo que com alguma constante realmente grande. Vou jogar com o otimista e supor que encontramos uma prova de P = N P com uma constante muito pequena. Talvez não seja provável, mas eu vou tentar dar algumas dicas sobre que tipo de coisas que aconteceria se pudéssemos resolver de forma eficiente todos os N P problemas.$P=NP$$P=NP$$NP$

• Compiladores: alguns programas de computador ficariam um pouco mais rápidos, uma vez que os compiladores usam a coloração gráfica para alocação de registros. Poderíamos alocar exatamente para um grande número de registros. Os compiladores existentes que usam uma solução aproximada (como gráficos de acordes) obteriam melhores resultados e aqueles que usassem uma solução exata seriam mais rápidos.

• Localização da instalação: as empresas poderiam encontrar o local ideal para instalar fábricas e abastecer depósitos para transportar para suas lojas, quando houver possivelmente milhares de lojas e fábricas. Provavelmente não seria uma grande melhoria em relação às aproximações modernas, mas reduziria os custos.

• Compra de passagens de avião: as passagens aéreas são estranhas, pois não seguem a igualdade dos triângulos. Às vezes, é mais barato voar de A -> B -> C do que diretamente de A -> C, algo que não aparece ao modelar distâncias. Seria fácil criar um site que encontre a sequência absolutamente mais barata de voos que visitam algumas cidades e começa e termina na sua cidade natal.

• Projeto de circuitos: circuitos elétricos em um chip são basicamente fórmulas booleanas. Coisas como minimização podem ser calculadas com eficiência, para que nosso hardware fique um pouco mais eficiente.

• Agendamento: louco por sua escola fazer dois exames ao mesmo tempo? Se sua escola puder quantos horários eles precisam, para que nenhum aluno tenha um conflito, ou com um número de horários, minimize o número de conflitos.$P=NP$

Esta é apenas uma amostra das aplicações práticas que veríamos se -completeness não eram uma barreira. Tenho certeza de que perdi muitos, mas se a construção em questão tivesse uma boa constante, as implicações seriam de grande alcance.$NP$

Não veremos necessariamente nenhum efeito. Suponha que alguém encontre um algoritmo que resolva 3SAT em variáveis ​​em 2 100 n operações básicas. Você não poderá executar esse algoritmo em nenhuma instância, pois leva muito tempo. Ou suponha que ela encontre um algoritmo em execução em n 100 operações básicas. Só poderemos usá-lo em instâncias 3SAT em uma única variável, pois, para mais variáveis, leva muito tempo.$n$$2^{100} n$$n^{100}$

Por outro lado, suponha que P NP e que mesmo a hipótese de tempo exponencial mais forte seja válida. Então, em geral, o 3SAT deve ser intratável. No entanto, os solucionadores de SAT parecem estar indo bem em certos problemas.$\neq$

O que está acontecendo aqui? Existem vários problemas com a pergunta P vs. NP:

1. Diz respeito apenas ao pior caso.
2. É apenas assintótico.
3. Todos os limites de tempo polinomiais são iguais.

Esses problemas lançam dúvidas sobre sua relevância para o mundo real. Agora pode acontecer que algum algoritmo realmente rápido seja encontrado para o 3SAT, tão rápido que até a criptografia simétrica se tornaria quebrável. Mas considero isso altamente improvável. Por outro lado, é perfeitamente consistente que P seja diferente de NP e considere prático; isso quebraria certos esquemas de criptografia de chave pública. Esta é uma situação provável que teria repercussões, mas não está relacionada à questão P vs. NP.

A questão P vs. NP pode ser natural do ponto de vista matemático, mas, na minha opinião, sua relevância prática é duvidosa. A pesquisa sobre a questão, por outro lado, pode ou não ter repercussões práticas; não é guiado por esse aspecto.

Uma leitura muito boa aqui é [1], onde Impagliazzo considera cinco possíveis "mundos" onde as relações entre classes de complexidade são diferentes. Por exemplo, em um mundo chamado Algoritmica (consulte a Seção 2.1), temos (ou algum outro "equivalente moral" válido, como N P ⊆ B P P ).$\sf P = NP$$\sf NP \subseteq BPP$

Na Algoritmica, praticamente qualquer problema de otimização seria trivial. Linguagens de programação podem ser linguagens onde uma espécie as propriedades que uma saída desejada deve ter em relação à entrada, em vez de especificar como a computação deve ser realizada. Os computadores também podem encontrar provas para qualquer teorema no tempo, aproximadamente a duração da prova. (Este ponto de vista é muito optimistas de curso, e depende de um algoritmo eficiente para algumas problema -completo).$\sf NP$

[1] Russell Impagliazzo. Uma visão pessoal da complexidade dos casos médios. Conferência da Complexidade, 1995.

Mesmo sem P = NP, os computadores atuais são incrivelmente poderosos.

• 12873891274647018937561708356916501047777612653914909670721635802187 podem ser fatorados por um único computador em menos de um segundo.
• Para tarefas mais difíceis, como sintetizar o layout elétrico de um chip a partir de uma descrição de nível superior de suas funções ou corrigir máscaras fotográficas para compensar artefatos do processo de fabricação, grupos de centenas de computadores trabalham um dia inteiro para permitir o impossível.
• Os computadores de hoje são capazes de provar teoremas matemáticos que nenhum ser humano foi capaz de provar, como as álgebras de Robins são booleanas ou que uma certa constante que é conjecturada como ilimitada ( Problema de Discrepância de Erdős ) é maior que 2.
• Programas de análise de código fonte estáticos são capazes de identificar vulnerabilidades como o bug do Heartbleed .
• Ferramentas de raciocínio automatizadas como prover9 ou o teorema do E-provador são capazes de provar a maioria das caracterizações algébricas comuns de semigrupos inversos e anéis fortemente regulares sem ajuda explícita.

Edit 22 Jan 2018 Descobri agora como deveria ter "interpretado" o texto citado no exemplo abaixo. Foi minha culpa, era necessário que o elemento inverso fosse único . Aqui está o meu arquivo de entrada de 22 de dezembro de 2014 ( addinvrig.in ) e aqui está o arquivo de entrada fixo de hoje ( addinvrigFixed.in ). A linha crucial é: (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).O poder das ferramentas de raciocínio automatizadas ainda é fascinante para mim, mesmo que elas não possam me impedir de interpretar mal os escritos de outras pessoas.

O uso de ferramentas de raciocínio automatizadas é surpreendentemente útil para mim, quando me deparo com teoremas citados onde não tenho certeza de como "interpretar" o texto :

$x, y \in S$$(x \cdot y)' = x' \cdot y = x \cdot y'$$x' \cdot y' = x \cdot y$
$a \in aS \cap Sa$$a \in S$$S$

Eu adaptei meus arquivos de entrada do prover9 para esse teorema e imediatamente mostrei um contra-exemplo para o teorema, conforme citado. Modificar levemente as suposições produziu muitos teoremas verdadeiros semelhantes, o que torna mais provável que Karvellas realmente tenha declarado e provado um teorema correto, que só foi citado incorretamente aqui. Pesquisando a referência desse teorema, apenas apareceu outro artigo que citava Karvellas ainda menos preciso .

Esta é uma coleção inacreditavelmente incompleta de resultados auxiliados por computador para problemas específicos que são intratáveis ​​em geral se P! = NP. Talvez essa coleção deixe claro para pelo menos alguns leitores que todos nós tendemos a subestimar os poderes dos computadores nesse domínio. Muitas outras respostas a essa pergunta parecem sugerir que não haveria grandes consequências se os computadores obtivessem (um pouco) melhor na solução de problemas intratáveis. Mas os computadores ficam melhores em resolver problemas intratáveis ​​o tempo todo (porque gasta bastante tempo e dinheiro para fazer isso acontecer), e isso tem consequências muito reais. Se P = NP fosse provado, talvez a conscientização sobre o que os computadores realmente possam fazer (ainda hoje) aumentaria, e mais pessoas usariam computadores para ajudá-los nessas tarefas. (PS: Estou convencido de que P! = NP,

Há muitas opiniões sobre as implicações reais de P = NP. Como visto em outras boas respostas, existem principalmente duas escolas de pensamento. Uma é que um algoritmo de tempo P pode ser muito difícil ou inviável de implementar devido a "anomalias inesperadas" associadas à abstração. por exemplo:

• o programa pode ser muito "grande" para codificar
• pode haver uma constante muito grande envolvida de tal forma que, para todas as instâncias ao alcance da "computação terrestre", elas ainda são de longa duração, ou seja, a eficiência não "entra em ação", exceto em instâncias muito grandes. sabe-se que alguns algoritmos realmente se encaixam nesse caso, como apontado recentemente por Knuth (pergunta 15)

Em geral, estou procurando mais foco em algoritmos que funcionam rapidamente com relação a problemas cujo tamanho, n, é viável. A maior parte da literatura atual é dedicada a algoritmos assintoticamente grandes, mas são úteis apenas quando n excede o tamanho do universo.

Um famoso estudo de caso é realizado por Impagliazzo, como citado por J. em outra resposta. Entretanto, seu ensaio foi extrapolado um pouco nesse meio tempo. Aqui está uma excelente nova referência de um especialista que aborda essa questão em uma espécie de cenário futuro de ficção científica, ch2 / p11. resumindo

O bilhete de ouro: P, NP e a busca do impossível por Lance Fortnow

• "se acontecer que P = NP e tivermos algoritmos eficientes para todos os problemas de NP, o mundo mudará de maneira a fazer a Internet parecer uma nota de rodapé na história. Não apenas seria impossível descrever todas essas mudanças, mas também o seria impossível prever as maiores implicações das novas tecnologias ".

• Algoritmo implementado rapidamente no supercomputador. A Boeing imediatamente contrata para obter um melhor design de asa para uma nova aeronave, permitindo que voe de Londres para Sydney sem escalas.

• Algoritmo de pesquisa usado para encontrar um novo algoritmo ainda mais rápido, otimizando a solução P = NP original. Termina com resultado de 42 milhões de linhas de código ininteligível. Chamado de "algoritmo Urbana"

• Algoritmo usado para encontrar tratamentos de câncer personalizados / quase curas taylored para indivíduos. cura câncer, AIDS, diabetes, mas o resfriado comum permanece um mistério

• O algoritmo de super escalonamento permite aos meteorologistas "fazer avanços incríveis na previsão do tempo, permitindo previsões precisas de temperatura, ventos, nebulosidade e precipitação quase um ano antes do tempo. Algoritmos similares agora salvam vidas ao prever com precisão tempestades, tornados e furacões, para que as pessoas possam prepare ou evacue conforme necessário. "

• Reconhecimento de face altamente preciso

• Computador pode reconstruir modelos 3D de uma cena em tempo real a partir de diferentes ângulos de câmera

• Os algoritmos de computador controlam as operações da câmera para eventos esportivos (em vez de controlados por seres humanos)

• Comentários e replays automatizados são gerados pelo algoritmo, incluindo ângulos e estatísticas bem escolhidos, e gerados em qualquer idioma em tempo real

• Esportes / beisebol de fantasia assumem nova dimensão com simulações de alta precisão

• Gosto da receita de alimentos aprimorado pelo algoritmo

• O algoritmo pode ser usado para "aprender praticamente qualquer coisa, incluindo o que produz boa arte, música popular e palavras que mexem com a alma. Lembre-se de que P = NP significa que o que podemos testar, podemos encontrar. Então, quando você tiver um algoritmo processo para reconhecer a grandeza, você pode usar o algoritmo novamente para encontrar rapidamente essa grandeza. "

• O político usa algoritmo de computador para reconhecer grandes discursos e gerar um que se encaixa nos padrões. A fala se torna viral na internet.

• As pessoas geram obras de arte completas a partir de arte incompleta / inacabada, como sinfonias. eles usam algoritmo para gerar novos registros Beatles / Elvis. Nova arte, romances, peças de teatro e poesia, por exemplo, comédia romântica com Humphrey Bogart / Julia Roberts.

• A Amazon pode criar um romance personalizado para indivíduos sob demanda. NBC cria séries de televisão de ação e aventura criadas inteiramente por computador

• Realidade virtual simulada em videogames, permitindo ações dos jogadores, em vez de um conjunto fixo de possíveis enredos.

• A aplicação da lei usa o algoritmo como "ferramenta incrível na solução de crimes, aparentemente fazendo o impossível na busca de suspeitos". O algoritmo de computador pode reconstruir faces prováveis ​​(para esboços compostos) usando apenas DNA. A polícia identifica um suspeito de assassinato usando uma pesquisa maciça no banco de dados de fotos da carteira de motorista alinhado com o esboço gerado (do DNA).

Infelizmente, pouco do que Fortnow descreve acima é suportado pela literatura científica atual, exceto talvez uma extrapolação imaginativa dos mundos de Impagliazzos. seria preciso muito mais para dissecar esse ponto a ponto, mas, para resumir, tudo parece divertido, mas fantástico / uma ilusão (ou talvez esse seja seu ponto velado). De fato, existem princípios científicos que estão em conflito com muitos dos itens. E note que Fortnow é um fã de esportes, então desenvolve uma metáfora extensa nessa área, mas isso poderia ser mais uma indicação de humanos pensando em ranhuras ?

Por exemplo, o "efeito borboleta" é conhecido por implicar que a previsão exata do tempo após um (digamos) horizonte de vários dias é impossível devido à "dependência sensível das condições iniciais" (e Fortnow mais tarde admitiu em seu blog críticas repetidas sobre exatamente isso ponto). Além disso, existem muitas evidências de que os computadores falham em tarefas altamente subjetivas ao ser humano, como gerar ou identificar arte influente (uma tarefa na qual mesmo os especialistas em seres humanos não conseguem consistentemente).

Na verdade, toda a questão está à beira de uma premissa contrafactual ou falsa . Observe que uma grande maioria de cientistas especialistas pesquisou pensar / acreditar, apesar da falta de provas incontestáveis ​​até agora, P ≠ NP. e é natural compará-lo com outras leis / restrições / limitações conhecidas como termodinâmica (por exemplo, impossibilidade de movimento perpétuo / energia livre ) e estatísticas, por exemplo, o "teorema do almoço sem almoço" .

Portanto, o ponto principal é que talvez até cientistas especialistas não possam prever exatamente o resultado de P = NP. Então, talvez a melhor resposta por enquanto seja admitir que os humanos não tenham uma boa resposta no momento.

P vs. NP, tecnicamente vs. moralmente

$O(n^2)$$O(n^{\lg^* n})$$2^{65536}+2^{1024}n^{256}$ Russell Impagliazzo disse uma vez que ele consideraria a P versus NP problema como essencialmente resolvido se alguém mostra SAT pode ser resolvido em$O(n^{\lg n})$

Então, o que acontece se P = NP é moralmente verdade?

$Q$$Q$verdade, todos esses problemas podem ser resolvidos muito rapidamente. Apenas para dar um exemplo, você pode aprender as melhores ponderações para modelos de aprendizado de máquina muito complicados. Você pode quebrar os protocolos de criptografia.

$\neq$

$\neq$

$\neq$

$\neq$

$\neq$

Se você sabe que deseja resolver um problema NP-complete não em entradas gerais, mas em entradas com propriedades específicas, não precisa se preocupar com o problema geral. Você só precisa resolver o problema mais simples. Infelizmente, muitas vezes não é fácil determinar com que tipo de dados você se importa na prática.

$\neq$

Que tipo de efeito quase imediato uma prova completa e precisa de P = NP, com uma solução fornecida, teria no mundo prático?

É provável que ocorram muitas coisas boas, mas ninguém se importaria.

O problema é que a base de (quase) toda a criptografia moderna se baseia na suposição de que P não é igual a NP. A criptografia que protege sua senha à medida que passa pela Internet e como é salva nos bancos de dados. A criptografia que protege os dados do cartão de crédito à medida que passa pela Internet ... A criptografia que protege os bilhões de transações financeiras diárias que vinculam nossa economia global ao organismo gigante que é.

Na melhor das hipóteses, P = NP significa que para. As pessoas voltam a usar dinheiro e os bancos tentam registrar esses saques em algum meio desconectado, já que as transações para um escritório central não são mais confiáveis. Isso dura talvez alguns meses até que uma melhor criptografia seja implementada globalmente. Melhor caso.

Na pior das hipóteses, P = NP significa que alguém quebra o mundo. A moeda é construída sobre o conceito de confiança. Você valoriza um dólar, porque confia que seu vizinho lhe dará um dólar em bens ou serviços por isso. Você valoriza o seu computador dizendo que possui 500 dólares no banco, porque pode passar o cartão e obter 500 dólares em bens e serviços ...

E se você não pudesse confiar nisso? Se P = NP, alguém poderia se passar por vários bancos, governo, pessoas - e efetivamente randomizar a quantidade de moeda em todas as contas. Exclua a moeda em todas as contas. Certamente, vários bancos têm backups para justificá-lo, mas há quanto tempo sua criptografia está quebrada? Quais transações foram boas e quais foram representadas? É impossível saber.

Uma vez que essa confiança é quebrada, o caos segue. Quaisquer benefícios de poder lidar com o Problema do Vendedor Viajante (por exemplo) são ignorados à medida que as pessoas lutam para se alimentar.

É provável que a realidade esteja em algum ponto intermediário, mas espero que isso mostre uma imagem suficientemente grande de quão importante é esse problema.

Irá ocorrer uma queda maciça nas despesas com equipamentos, eletricidade e abordagens em nuvem. Muitas coisas estão sendo calculadas com força bruta agora, ou aproximações que ainda usam alguma força bruta pesada. Não faremos mais todos esses cálculos de força bruta paralelizados em massa.

Esse não é, de modo algum, o único uso da computação em nuvem, mas ainda será um fator perceptível no uso de energia, processamento na nuvem etc. Apenas a economia de energia pode ser notada em nossa pegada de carbono.

A IA também se tornará muito melhor. Finalmente, podemos ter um computador que pode ser o melhor jogador de GO, e sua calculadora gráfica irá derrotá-lo no xadrez.

$\ne$

E a conjectura que está sendo contestada não significa que todos os problemas de utilidade prática seriam resolvidos em um piscar de olhos. Em primeiro lugar, eles ainda podem ser mais difíceis do que NP.