Problema P versus NP - P versus NP problem

O problema P versus NP é um grande problema não resolvido na ciência da computação . Ele pergunta se cada problema cuja solução pode ser verificada rapidamente também pode ser resolvido rapidamente.

O termo informal rapidamente , usado acima, significa a existência de um algoritmo resolvendo a tarefa que é executado em tempo polinomial , de modo que o tempo para completar a tarefa varia como uma função polinomial no tamanho da entrada para o algoritmo (em oposição a, digamos, tempo exponencial ). A classe geral de questões para a qual algum algoritmo pode fornecer uma resposta em tempo polinomial é " P " ou " classe P ". Para algumas perguntas, não há uma maneira conhecida de encontrar uma resposta rápida, mas se houver informações que mostrem qual é a resposta, é possível verificar a resposta rapidamente. A classe de questões para a qual uma resposta pode ser verificada em tempo polinomial é NP , que significa "tempo polinomial não determinístico".

Uma resposta à questão P versus NP determinaria se problemas que podem ser verificados em tempo polinomial também podem ser resolvidos em tempo polinomial. Se for descoberto que P ≠ NP, o que é amplamente aceito, significaria que existem problemas em NP que são mais difíceis de computar do que de verificar: eles não poderiam ser resolvidos em tempo polinomial, mas a resposta poderia ser verificada em tempo polinomial .

O problema é considerado por muitos como o problema aberto mais importante na ciência da computação . Além de ser um problema importante na teoria computacional , uma prova de qualquer maneira teria implicações profundas para matemática, criptografia , pesquisa de algoritmos, inteligência artificial , teoria dos jogos , processamento multimídia, filosofia , economia e muitos outros campos.

É um dos sete Problemas do Prêmio do Milênio selecionados pelo Clay Mathematics Institute , cada um dos quais traz um prêmio de US $ 1.000.000 pela primeira solução correta.

Exemplo

Considere o Sudoku , um jogo em que o jogador recebe uma grade de números parcialmente preenchida e tenta completá-la seguindo certas regras. Dada uma grade de Sudoku incompleta, de qualquer tamanho, existe pelo menos uma solução legal? Qualquer solução proposta é facilmente verificada, e o tempo para verificar uma solução cresce lentamente (polinomialmente) conforme a grade fica maior. No entanto, todos os algoritmos conhecidos para encontrar soluções levam, para exemplos difíceis, um tempo que cresce exponencialmente à medida que a grade fica maior. Portanto, o Sudoku está em NP (rapidamente verificável), mas não parece estar em P (rapidamente resolvível). Milhares de outros problemas parecem semelhantes, no sentido de que são rápidos para verificar, mas lentos para resolver. Os pesquisadores mostraram que muitos dos problemas em NP têm a propriedade extra de que uma solução rápida para qualquer um deles poderia ser usada para construir uma solução rápida para qualquer outro problema em NP, uma propriedade chamada NP-completude . Décadas de busca não produziram uma solução rápida para nenhum desses problemas, então a maioria dos cientistas suspeita que nenhum desses problemas pode ser resolvido rapidamente. Isso, no entanto, nunca foi provado.

História

A declaração precisa do problema P versus NP foi introduzida em 1971 por Stephen Cook em seu artigo seminal "A complexidade dos procedimentos de prova de teoremas" (e independentemente por Leonid Levin em 1973).

Embora o problema P versus NP tenha sido definido formalmente em 1971, havia indícios anteriores dos problemas envolvidos, a dificuldade da prova e as consequências potenciais. Em 1955, o matemático John Nash escreveu uma carta à NSA , onde especulou que quebrar um código suficientemente complexo exigiria um tempo exponencial no comprimento da chave. Se provado (e Nash foi adequadamente cético), isso implicaria no que agora é chamado de P ≠ NP, uma vez que uma chave proposta pode ser facilmente verificada em tempo polinomial. Outra menção do problema subjacente ocorreu em uma carta de 1956 escrita por Kurt Gödel a John von Neumann . Gödel perguntou se a prova de teorema (agora conhecida como co-NP-completa ) poderia ser resolvida em tempo quadrático ou linear e apontou uma das consequências mais importantes - se assim for, a descoberta de provas matemáticas poderia ser automatizada.

Contexto

A relação entre as classes de complexidade P e NP é estudada na teoria da complexidade computacional , a parte da teoria da computação que trata dos recursos necessários durante a computação para resolver um determinado problema. Os recursos mais comuns são tempo (quantas etapas são necessárias para resolver um problema) e espaço (quanta memória é necessária para resolver um problema).

Nessa análise, é necessário um modelo do computador para o qual o tempo deve ser analisado. Normalmente, esses modelos assumem que o computador é determinístico (dado o estado atual do computador e quaisquer entradas, há apenas uma ação possível que o computador pode realizar) e sequencial (ele executa ações uma após a outra).

Nesta teoria, a classe P consiste em todos aqueles problemas de decisão (definidos abaixo ) que podem ser resolvidos em uma máquina sequencial determinística em um período de tempo que é polinomial no tamanho da entrada; a classe NP consiste em todos aqueles problemas de decisão cujas soluções positivas podem ser verificadas em tempo polinomial a partir da informação correta, ou de forma equivalente, cuja solução pode ser encontrada em tempo polinomial em uma máquina não determinística . Claramente, P ⊆ NP. Indiscutivelmente, a maior questão em aberto na ciência da computação teórica diz respeito à relação entre essas duas classes:

P é igual a NP?

Desde 2002, William Gasarch conduziu três pesquisas de opinião sobre esta e outras questões relacionadas. Confiança de que P ≠ NP vem aumentando - em 2019, 88% acreditavam em P ≠ NP, contra 83% em 2012 e 61% em 2002. Quando restritas a especialistas, as respostas de 2019 passaram a ser de 99% acreditam em P ≠ NP. Essas pesquisas não implicam em nada sobre se P = NP é verdadeiro, como afirma o próprio Gasarca: ″ Isso não nos deixa mais perto de resolver P =? NP ou de saber quando será resolvido, mas tenta ser um objetivo relatório sobre a opinião subjetiva desta época. ″

NP-completude

Diagrama de Euler para o conjunto de problemas P , NP , NP-completo e NP-difícil (excluindo a linguagem vazia e seu complemento, que pertencem a P, mas não são NP-completos)

Para atacar a questão P = NP, o conceito de NP-completude é muito útil. Problemas NP-completos são um conjunto de problemas para os quais qualquer outro problema NP-completo pode ser reduzido em tempo polinomial e cuja solução ainda pode ser verificada em tempo polinomial. Ou seja, qualquer problema NP pode ser transformado em qualquer um dos problemas NP-completos. Informalmente, um problema NP-completo é um problema NP que é pelo menos tão "difícil" quanto qualquer outro problema em NP.

Os problemas NP-difíceis são aqueles pelo menos tão difíceis quanto os problemas NP; ou seja, todos os problemas NP podem ser reduzidos (em tempo polinomial) a eles. Os problemas NP-difíceis não precisam estar no NP; ou seja, eles não precisam ter soluções verificáveis ​​em tempo polinomial.

Por exemplo, o problema de satisfatibilidade booleana é NP-completo pelo teorema de Cook-Levin , então qualquer instância de qualquer problema em NP pode ser transformada mecanicamente em uma instância do problema de satisfatibilidade booleana em tempo polinomial. O problema de satisfatibilidade booleana é um dos muitos problemas NP-completos. Se qualquer problema NP-completo estiver em P, seguir-se-ia que P = NP. No entanto, muitos problemas importantes mostraram ser NP-completos e nenhum algoritmo rápido para qualquer um deles é conhecido.

Com base apenas na definição, não é óbvio que existam problemas NP-completos; entretanto, um problema NP-completo trivial e planejado pode ser formulado como segue: dada a descrição de uma máquina de Turing M garantida para parar em tempo polinomial, existe uma entrada de tamanho polinomial que M aceitará? Está em NP porque (dada uma entrada) é simples verificar se M aceita a entrada simulando M ; é NP-completo porque o verificador para qualquer instância particular de um problema em NP pode ser codificado como uma máquina de tempo polinomial M que leva a solução a ser verificada como entrada. Então, a questão de saber se a instância é uma instância sim ou não é determinada pela existência de uma entrada válida.

O primeiro problema natural comprovado como NP-completo foi o problema de satisfatibilidade booleana, também conhecido como SAT. Como observado acima, este é o teorema de Cook-Levin; sua prova de que a satisfatibilidade é NP-completa contém detalhes técnicos sobre as máquinas de Turing no que se refere à definição de NP. No entanto, depois que esse problema foi provado ser NP-completo, a prova por redução forneceu uma maneira mais simples de mostrar que muitos outros problemas também são NP-completos, incluindo o jogo Sudoku discutido anteriormente. Nesse caso, a prova mostra que uma solução de Sudoku em tempo polinomial também poderia ser usada para completar quadrados latinos em tempo polinomial. Isso, por sua vez, dá uma solução para o problema de particionar grafos tripartidos em triângulos, que poderiam então ser usados ​​para encontrar soluções para o caso especial de SAT conhecido como 3-SAT, que então fornece uma solução para satisfatibilidade booleana geral. Assim, uma solução em tempo polinomial para o Sudoku leva, por uma série de transformações mecânicas, a uma solução em tempo polinomial de satisfatibilidade, que por sua vez pode ser usada para resolver qualquer outro problema NP em tempo polinomial. Usando transformações como essa, uma vasta classe de problemas aparentemente não relacionados são todos redutíveis uns aos outros e, em certo sentido, "o mesmo problema".

Problemas mais difíceis

Embora não se saiba se P = NP, problemas fora de P são conhecidos. Assim como a classe P é definida em termos de tempo de execução polinomial, a classe EXPTIME é o conjunto de todos os problemas de decisão que possuem tempo de execução exponencial . Em outras palavras, qualquer problema em EXPTIME pode ser resolvido por uma máquina de Turing determinística em tempo O (2 ^{p ( n )} ), onde p ( n ) é uma função polinomial de n . Um problema de decisão é EXPTIME-completo se estiver em EXPTIME, e todo problema em EXPTIME tem uma redução muitos-um de tempo polinomial . Vários problemas são conhecidos como EXPTIME-completos. Como pode ser mostrado que P ≠ EXPTIME, esses problemas estão fora de P e, portanto, requerem mais do que tempo polinomial. Na verdade, pelo teorema da hierarquia de tempo , eles não podem ser resolvidos em significativamente menos do que o tempo exponencial. Exemplos incluem encontrar uma estratégia perfeita para xadrez posições sobre um N × N bordo e problemas semelhantes para outros jogos de tabuleiro.

O problema de decidir a verdade de uma declaração na aritmética de Presburger requer ainda mais tempo. Fischer e Rabin provaram em 1974 que todo algoritmo que decide a verdade das declarações Presburger de comprimento n tem um tempo de execução de pelo menos para alguma constante c . Conseqüentemente, o problema é conhecido por precisar de mais do que tempo de execução exponencial. Ainda mais difíceis são os problemas indecidíveis , como o problema da parada . Eles não podem ser completamente resolvidos por nenhum algoritmo, no sentido de que, para qualquer algoritmo específico, há pelo menos uma entrada para a qual esse algoritmo não produzirá a resposta certa; ele produzirá a resposta errada, terminará sem dar uma resposta conclusiva ou, de outra forma, funcionará para sempre sem produzir qualquer resposta. ${\ displaystyle 2 ^ {2 ^ {cn}}}$

Também é possível considerar outras questões além dos problemas de decisão. Uma dessas classes, que consiste em problemas de contagem, é chamada de #P : enquanto um problema NP pergunta "Existem soluções?", O problema #P correspondente pergunta "Quantas soluções existem?" Claramente, um problema #P deve ser pelo menos tão difícil quanto o problema NP correspondente, uma vez que uma contagem de soluções informa imediatamente se pelo menos uma solução existe, se a contagem for maior que zero. Surpreendentemente, alguns problemas #P considerados difíceis correspondem a problemas P fáceis (por exemplo, de tempo linear). Para esses problemas, é muito fácil dizer se existem soluções, mas é muito difícil dizer quantas. Muitos desses problemas são # P-completos e, portanto, estão entre os problemas mais difíceis em #P, uma vez que uma solução em tempo polinomial para qualquer um deles permitiria uma solução em tempo polinomial para todos os outros problemas #P.

Problemas em NP não conhecidos por estarem em P ou NP-completo

Em 1975, Richard E. Ladner mostrou que se P ≠ NP então existem problemas em NP que não estão em P nem NP-completos. Esses problemas são chamados de problemas intermediários NP. O problema do isomorfismo de grafos , o problema do logaritmo discreto e o problema da fatoração de inteiros são exemplos de problemas que se acredita serem NP-intermediários. Eles são alguns dos poucos problemas NP que não se sabe estarem em P ou como NP-completos.

O problema de isomorfismo de grafos é o problema computacional de determinar se dois grafos finitos são isomórficos . Um importante problema não resolvido na teoria da complexidade é se o problema de isomorfismo de grafos está em P, NP-completo ou NP-intermediário. A resposta não é conhecida, mas acredita-se que o problema pelo menos não seja NP-completo. Se o isomorfismo do gráfico for NP-completo, a hierarquia de tempo polinomial cai para seu segundo nível. Uma vez que é amplamente aceito que a hierarquia polinomial não entra em colapso para nenhum nível finito, acredita-se que o isomorfismo do grafo não é NP-completo. O melhor algoritmo para este problema, devido a László Babai , roda em tempo quase polinomial .

O problema de fatoração de inteiros é o problema computacional de determinar a fatoração principal de um dado inteiro. Formulado como um problema de decisão, é o problema de decidir se a entrada tem um fator menor que k . Nenhum algoritmo de fatoração de números inteiros eficiente é conhecido, e esse fato forma a base de vários sistemas criptográficos modernos, como o algoritmo RSA . O problema de fatoração de inteiros está em NP e em co-NP (e mesmo em UP e co-UP). Se o problema for NP-completo, a hierarquia de tempo polinomial entrará em colapso para seu primeiro nível (ou seja, NP = co-NP). O algoritmo mais conhecido para fatoração de inteiros é a peneira de campo de número geral , que leva o tempo esperado

${\ displaystyle O \ left (\ exp \ left (\ left ({\ tfrac {64n} {9}} \ log (2) \ right) ^ {\ frac {1} {3}} \ left (\ log ( n \ log (2)) \ direita) ^ {\ frac {2} {3}} \ direita) \ direita)}$

para fatorar um número inteiro de n bits. No entanto, o algoritmo quântico mais conhecido para esse problema, o algoritmo de Shor , é executado em tempo polinomial, embora isso não indique onde está o problema com relação às classes de complexidade não quântica .

P significa "fácil"?

O gráfico mostra o tempo de execução versus o tamanho do problema para um problema de mochila de um algoritmo especializado de última geração. O ajuste quadrático sugere que a complexidade algorítmica do problema é O ((log ( n )) ² ).

Toda a discussão acima assumiu que P significa "fácil" e "não em P" significa "difícil", uma suposição conhecida como tese de Cobham . É uma suposição comum e razoavelmente precisa na teoria da complexidade; no entanto, há algumas ressalvas.

Primeiro, nem sempre é verdade na prática. Um algoritmo polinomial teórico pode ter fatores ou expoentes constantes extremamente grandes, tornando-o impraticável. Por exemplo, o problema de decidir se um gráfico G contém H como um menor , em que H é fixa, pode ser resolvido em um tempo de execução de S ( n ² ), onde n é o número de vértices em L . No entanto, a notação O grande esconde uma constante que depende superexponentially em H . A constante é maior do que (usando Notação de Knuth ), e onde H é o número de vértices em H . ${\ displaystyle 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (h / 2)))}$

Por outro lado, mesmo se um problema se mostrar NP-completo, e mesmo se P ≠ NP, ainda pode haver abordagens eficazes para lidar com o problema na prática. Existem algoritmos para muitos problemas NP-completos, como o problema da mochila , o problema do caixeiro viajante e o problema da satisfatibilidade booleana , que podem resolver de forma otimizada muitas instâncias do mundo real em um tempo razoável. A complexidade empírica de caso médio (tempo vs. tamanho do problema) de tais algoritmos pode ser surpreendentemente baixa. Um exemplo é o algoritmo simplex em programação linear , que funciona surpreendentemente bem na prática; apesar de ter complexidade de tempo exponencial de pior caso , ele funciona em paridade com os algoritmos de tempo polinomial mais conhecidos.

Finalmente, existem tipos de cálculos que não estão em conformidade com o modelo da máquina de Turing no qual P e NP são definidos, como computação quântica e algoritmos aleatórios .

Razões para acreditar que P ≠ NP ou P = NP

Cozinhe fornece uma correção do problema em THE P versus NP como: Does P = NP ? . De acordo com as pesquisas, a maioria dos cientistas da computação acredita que P ≠ NP. Uma razão chave para essa crença é que, após décadas de estudo desses problemas, ninguém foi capaz de encontrar um algoritmo de tempo polinomial para qualquer um dos mais de 3.000 problemas NP-completos importantes conhecidos (ver Lista de problemas NP-completos ). Esses algoritmos foram buscados muito antes que o conceito de NP-completude fosse definido ( os 21 problemas NP-completos de Karp , entre os primeiros encontrados, eram todos problemas existentes bem conhecidos no momento em que se mostrava NP-completo). Além disso, o resultado P = NP implicaria muitos outros resultados surpreendentes que atualmente se acredita serem falsos, como NP = co-NP e P = PH .

Também é argumentado intuitivamente que a existência de problemas que são difíceis de resolver, mas para os quais as soluções são fáceis de verificar, coincide com a experiência do mundo real.

Se P = NP, então o mundo seria um lugar profundamente diferente do que costumamos supor que seja. Não haveria nenhum valor especial em "saltos criativos", nenhuma lacuna fundamental entre resolver um problema e reconhecer a solução depois de encontrada.

-  Scott Aaronson , UT Austin

Por outro lado, alguns pesquisadores acreditam que há excesso de confiança em acreditar que P ≠ NP e que os pesquisadores também devem explorar as provas de P = NP. Por exemplo, em 2002 essas declarações foram feitas:

O principal argumento a favor de P ≠ NP é a total falta de progresso fundamental na área de busca exaustiva. Este é, em minha opinião, um argumento muito fraco. O espaço dos algoritmos é muito grande e estamos apenas no início de sua exploração. [...] A resolução do Último Teorema de Fermat também mostra que questões muito simples podem ser resolvidas apenas por teorias muito profundas.

-  Moshe Y. Vardi , Rice University

Estar apegado a uma especulação não é um bom guia para o planejamento de pesquisa. Deve-se sempre tentar as duas direções para cada problema. O preconceito fez com que matemáticos famosos não conseguissem resolver problemas famosos cuja solução era contrária às suas expectativas, embora eles tivessem desenvolvido todos os métodos exigidos.

-  Anil Nerode , Universidade Cornell

Consequências da solução

Uma das razões pelas quais o problema atrai tanta atenção são as consequências de algumas respostas possíveis. Qualquer direção de resolução avançaria enormemente a teoria e talvez também tivesse enormes consequências práticas.

P = NP

Uma prova de que P = NP pode ter consequências práticas surpreendentes se a prova levar a métodos eficientes para resolver alguns dos problemas importantes em NP. As consequências potenciais, tanto positivas quanto negativas, surgem já que vários problemas NP-completos são fundamentais em muitos campos.

Também é muito possível que uma prova não leve a algoritmos práticos para problemas NP-completos. A formulação do problema não requer que o polinômio delimitador seja pequeno ou mesmo especificamente conhecido. Uma prova não construtiva pode mostrar que existe uma solução sem especificar um algoritmo para obtê-la ou um limite específico. Mesmo se a prova for construtiva, mostrando um polinômio delimitador explícito e detalhes algorítmicos, se o polinômio não for de ordem muito baixa, o algoritmo pode não ser suficientemente eficiente na prática. Nesse caso, a prova inicial seria de interesse principalmente para os teóricos, mas o conhecimento de que as soluções de tempo polinomial são possíveis certamente estimularia a pesquisa de métodos melhores (e possivelmente práticos) para alcançá-las.

Um exemplo de um campo que poderia ser desarraigado por uma solução mostrando P = NP é a criptografia , que depende de certos problemas serem difíceis. Uma solução construtiva e eficiente para um problema NP-completo, como o 3-SAT , quebraria a maioria dos criptossistemas existentes, incluindo:

• Implementações existentes de criptografia de chave pública , uma base para muitos aplicativos de segurança modernos, como transações financeiras seguras pela Internet.
• Cifras simétricas , como AES ou 3DES , usadas para criptografar dados de comunicação.
• Hash criptográfico , que sustenta criptomoedas de blockchain , como Bitcoin , e é usado para autenticar atualizações de software. Para essas aplicações, o problema de encontrar uma pré-imagem que efetua hashes para um determinado valor deve ser difícil para ser útil e, idealmente, deve exigir um tempo exponencial. No entanto, se P = NP, então encontrar uma pré-imagem M pode ser feito em tempo polinomial, através da redução para SAT.

Estes precisariam ser modificados ou substituídos por soluções teoricamente seguras da informação não inerentemente baseadas na desigualdade P-NP.

Por outro lado, existem enormes consequências positivas que resultariam de tornar tratáveis ​​muitos problemas matematicamente intratáveis ​​atualmente. Por exemplo, muitos problemas em pesquisa operacional são NP-completos, como alguns tipos de programação inteira e o problema do caixeiro viajante . Soluções eficientes para esses problemas teriam enormes implicações para a logística. Muitos outros problemas importantes, como alguns problemas na previsão da estrutura da proteína , também são NP-completos; se esses problemas fossem resolvidos com eficiência, isso poderia estimular avanços consideráveis ​​nas ciências da vida e na biotecnologia.

Mas essas mudanças podem perder importância em comparação com a revolução que um método eficiente para resolver problemas NP-completos causaria na própria matemática. Gödel, em seus primeiros pensamentos sobre a complexidade computacional, observou que um método mecânico que poderia resolver qualquer problema revolucionaria a matemática:

Se realmente existisse uma máquina com φ (n) ∼ k ⋅ n (ou mesmo ∼ k ⋅ n ² ), isso teria consequências da maior importância. Ou seja, obviamente significaria que, apesar da indecidibilidade do Entscheidungsproblem , o trabalho mental de um matemático sobre questões de Sim ou Não poderia ser completamente substituído por uma máquina. Afinal, bastaria escolher o número natural n tão grande que, quando a máquina não fornece um resultado, não faz sentido pensar mais no problema.

Da mesma forma, Stephen Cook (assumindo não apenas uma prova, mas um algoritmo praticamente eficiente) diz

... transformaria a matemática, permitindo que um computador encontrasse uma prova formal de qualquer teorema que tenha uma prova de comprimento razoável, uma vez que as provas formais podem ser facilmente reconhecidas em tempo polinomial. Problemas de exemplo podem incluir todos os problemas de prêmios do CMI .

Pesquisadores matemáticos passam suas carreiras tentando provar teoremas, e algumas provas levaram décadas ou até séculos para serem descobertas depois que os problemas foram declarados - por exemplo, o Último Teorema de Fermat levou mais de três séculos para ser provado. Um método garantido para encontrar provas para teoremas, caso existisse um de tamanho "razoável", essencialmente encerraria essa luta.

Donald Knuth afirmou que passou a acreditar que P = NP, mas está reservado sobre o impacto de uma possível prova:

[...] se você imaginar um número M que é finito, mas incrivelmente grande - como digamos o número 10 ↑↑↑↑ 3 discutido em meu artigo sobre "lidar com a finitude" - então há um grande número de algoritmos possíveis que fazem n ^M operações bit a bit ou adição ou deslocamento em n bits dados, e é realmente difícil acreditar que todos esses algoritmos falhem. Meu ponto principal, entretanto, é que não acredito que a igualdade P = NP venha a ser útil mesmo se for provada, porque tal prova quase certamente não será construtiva.

Diagrama de classes de complexidade desde que P  ≠  NP. A existência de problemas dentro de NP, mas fora de P e NP-completo, sob essa suposição, foi estabelecida pelo teorema de Ladner .

P ≠ NP

Uma prova que mostrou que P ≠ NP faltaria os benefícios computacionais práticos de uma prova de que P = NP, mas representaria um avanço muito significativo na teoria da complexidade computacional e forneceria orientação para pesquisas futuras. Permitiria mostrar de forma formal que muitos problemas comuns não podem ser resolvidos de forma eficiente, de modo que a atenção dos pesquisadores pode ser focada em soluções parciais ou soluções para outros problemas. Devido à crença generalizada em P ≠ NP, muito desse enfoque de pesquisa já ocorreu.

Além disso, P ≠ NP ainda deixa em aberto a complexidade de caso médio de problemas difíceis em NP. Por exemplo, é possível que SAT exija tempo exponencial no pior caso, mas que quase todas as instâncias selecionadas aleatoriamente sejam resolvidas com eficiência. Russell Impagliazzo descreveu cinco "mundos" hipotéticos que poderiam resultar de diferentes resoluções possíveis para a questão de complexidade de caso médio. Estes variam de "Algoritmica", onde P = NP e problemas como SAT podem ser resolvidos de forma eficiente em todas as instâncias, a "Criptomania", onde P ≠ NP e gerar instâncias difíceis de problemas fora de P é fácil, com três possibilidades intermediárias refletindo diferentes possíveis distribuições de dificuldade sobre instâncias de problemas NP-difíceis. O "mundo" onde P ≠ NP mas todos os problemas em NP são tratáveis ​​no caso médio é chamado de "Heurística" no artigo. Um workshop da Universidade de Princeton em 2009 estudou o status dos cinco mundos.

Resultados sobre dificuldade de prova

Embora o próprio problema P = NP permaneça aberto, apesar de um prêmio de um milhão de dólares e uma enorme quantidade de pesquisas dedicadas, os esforços para resolver o problema levaram a várias novas técnicas. Em particular, algumas das pesquisas mais frutíferas relacionadas ao problema P = NP mostraram que as técnicas de prova existentes não são poderosas o suficiente para responder à pergunta, sugerindo assim que novas abordagens técnicas são necessárias.

Como evidência adicional para a dificuldade do problema, essencialmente todas as técnicas de prova conhecidas na teoria da complexidade computacional caem em uma das seguintes classificações, cada uma das quais é sabidamente insuficiente para provar que P ≠ NP:

Essas barreiras são outra razão pela qual os problemas NP-completos são úteis: se um algoritmo de tempo polinomial pode ser demonstrado para um problema NP-completo, isso resolveria o problema P = NP de uma forma não excluída pelos resultados acima.

Essas barreiras também levaram alguns cientistas da computação a sugerir que o problema P versus NP pode ser independente dos sistemas de axioma padrão como o ZFC (não pode ser provado ou refutado dentro deles). A interpretação de um resultado de independência pode ser que nenhum algoritmo de tempo polinomial existe para qualquer problema NP-completo, e tal prova não pode ser construída em (por exemplo) ZFC, ou que algoritmos de tempo polinomial para problemas NP-completos podem existir, mas é impossível provar no ZFC que tais algoritmos estão corretos. No entanto, se puder ser mostrado, usando técnicas do tipo que são atualmente conhecidas como aplicáveis, que o problema não pode ser decidido mesmo com suposições muito mais fracas estendendo os axiomas de Peano (PA) para aritmética inteira, então necessariamente existiria quase- Algoritmos de tempo polinomial para todos os problemas em NP. Portanto, se alguém acredita (como muitos teóricos da complexidade fazem) que nem todos os problemas em NP têm algoritmos eficientes, seguir-se-ia que as provas de independência usando essas técnicas não podem ser possíveis. Além disso, este resultado implica que provar a independência de PA ou ZFC usando técnicas atualmente conhecidas não é mais fácil do que provar a existência de algoritmos eficientes para todos os problemas em NP.

Soluções reivindicadas

Embora o problema P versus NP seja geralmente considerado sem solução, muitos pesquisadores amadores e alguns profissionais reivindicaram soluções. Gerhard J. Woeginger mantém uma lista que, a partir de 2016, contém 62 supostas provas de P = NP, 50 provas de P ≠ NP, 2 provas de que o problema é improvável e uma prova de que é indecidível. Claramente, pelo menos 53 dessas provas estão erradas. Algumas tentativas de resolver P versus NP receberam breve atenção da mídia, embora essas tentativas tenham sido refutadas.

Caracterizações lógicas

O problema P = NP pode ser reafirmado em termos de certas classes expressáveis ​​de afirmações lógicas, como resultado do trabalho em complexidade descritiva .

Considere todas as linguagens de estruturas finitas com uma assinatura fixa, incluindo uma relação de ordem linear . Então, todas essas linguagens em P podem ser expressas em lógica de primeira ordem com a adição de um combinador de ponto fixo mínimo adequado . Efetivamente, isso, em combinação com a ordem, permite a definição de funções recursivas. Contanto que a assinatura contenha pelo menos um predicado ou função além da relação de ordem distinta, de modo que a quantidade de espaço necessário para armazenar tais estruturas finitas seja na verdade polinomial no número de elementos na estrutura, isso caracteriza precisamente P.

Da mesma forma, NP é o conjunto de linguagens expressáveis ​​na lógica existencial de segunda ordem - isto é, a lógica de segunda ordem restrita para excluir a quantificação universal sobre relações, funções e subconjuntos. As linguagens na hierarquia polinomial , PH , correspondem a todas as lógicas de segunda ordem. Assim, a questão "P é um subconjunto próprio de NP" pode ser reformulada como "a lógica existencial de segunda ordem é capaz de descrever linguagens (de estruturas finitas linearmente ordenadas com assinatura não trivial) que a lógica de primeira ordem com menos ponto fixo não pode?" . A palavra "existencial" pode até ser retirada da caracterização anterior, uma vez que P = NP se e somente se P = PH (já que o primeiro estabeleceria que NP = co-NP, o que por sua vez implica que NP = PH).

Algoritmos de tempo polinomial

Nenhum algoritmo para qualquer problema NP-completo é conhecido por ser executado em tempo polinomial. No entanto, existem algoritmos conhecidos para problemas NP-completos com a propriedade de que se P = NP, então o algoritmo roda em tempo polinomial ao aceitar instâncias (embora com constantes enormes, tornando o algoritmo impraticável). No entanto, esses algoritmos não se qualificam como tempo polinomial porque seu tempo de execução em instâncias rejeitadas não é polinomial. O algoritmo a seguir, devido a Levin (sem qualquer citação), é um exemplo abaixo. Ele aceita corretamente a linguagem NP-completa SUBSET-SUM . Ele é executado em tempo polinomial nas entradas que estão em SUBSET-SUM se e somente se P = NP:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

Se, e somente se, P = NP, então este é um algoritmo de tempo polinomial que aceita uma linguagem NP-completa. "Aceitar" significa que dá respostas "sim" em tempo polinomial, mas pode ser executado para sempre quando a resposta for "não" (também conhecido como semi-algoritmo ).

Este algoritmo é extremamente impraticável, mesmo se P = NP. Se o programa mais curto que pode resolver SUBSET-SUM em tempo polinomial tiver b bits de comprimento, o algoritmo acima tentará pelo menos 2 ^b - 1 outros programas primeiro.

Definições formais

P e NP

Conceitualmente falando, um problema de decisão é um problema que toma como entrada uma seqüência de w mais de uma Σ alfabeto, e saídas "sim" ou "não". Se houver um algoritmo (digamos uma máquina de Turing ou um programa de computador com memória ilimitada) que pode produzir a resposta correta para qualquer string de entrada de comprimento n em no máximo cn ^k passos, onde k e c são constantes independentes da string de entrada , então dizemos que o problema pode ser resolvido em tempo polinomial e o colocamos na classe P. Formalmente, P é definido como o conjunto de todas as linguagens que podem ser decididas por uma máquina de Turing em tempo polinomial determinística. Isso é,

${\ displaystyle \ mathbf {P} = \ {L: L = L (M) {\ text {para alguma máquina de Turing de tempo polinomial determinística}} M \}}$

Onde

${\ displaystyle L (M) = \ {w \ in \ Sigma ^ {*}: M {\ text {aceita}} w \}}$

e uma máquina de Turing determinística em tempo polinomial é uma máquina de Turing determinística M que satisfaz as duas condições a seguir:

1. M para em todas as entradas w e
2. existe tal que , onde O se refere à grande notação O e${\ displaystyle k \ in N}$${\ displaystyle T_ {M} (n) \ in O (n ^ {k})}$

${\ displaystyle T_ {M} (n) = \ max \ {t_ {M} (w): w \ in \ Sigma ^ {*}, | w | = n \}}$

${\ displaystyle t_ {M} (w) = {\ text {número de passos}} M {\ text {leva para parar na entrada}} w.}$

NP pode ser definido de forma semelhante usando máquinas de Turing não determinísticas (a forma tradicional). No entanto, uma abordagem moderna para definir NP é usar o conceito de certificado e verificador . Formalmente, NP é definido como o conjunto de línguas sobre um alfabeto finito que possui um verificador que roda em tempo polinomial, onde a noção de "verificador" é definida como segue.

Seja L uma linguagem sobre um alfabeto finito, Σ.

L ∈ NP se, e somente se, existe uma relação binária e um inteiro positivo k tal que as seguintes duas condições sejam satisfeitas: ${\ displaystyle R \ subset \ Sigma ^ {*} \ times \ Sigma ^ {*}}$

1. Para todos , de forma que ( x , y ) ∈ R e${\ displaystyle x \ in \ Sigma ^ {*}}$${\ displaystyle x \ in L \ Leftrightarrow \ exists y \ in \ Sigma ^ {*}}$${\ displaystyle | y | \ in O (| x | ^ {k})}$ ; e
2. a língua mais é decidível por uma máquina de Turing determinística em tempo polinomial.${\ displaystyle L_ {R} = \ {x \ #y: (x, y) \ in R \}}$${\ displaystyle \ Sigma \ cup \ {\ # \}}$

Uma máquina de Turing que decide L _R é chamado um verificador para L e uma y tal que ( x , y ) ∈ R é chamado um certificado de adesão de x em L .

Em geral, um verificador não precisa ser de tempo polinomial. Porém, para que L esteja em NP, deve haver um verificador que execute em tempo polinomial.

Exemplo

Deixar

${\ displaystyle \ mathrm {COMPOSITE} = \ left \ {x \ in \ mathbb {N} \ mid x = pq {\ text {para inteiros}} p, q> 1 \ right \}}$

${\ displaystyle R = \ left \ {(x, y) \ in \ mathbb {N} \ times \ mathbb {N} \ mid 1 <y \ leq {\ sqrt {x}} {\ text {e}} y {\ text {divide}} x \ right \}.}$

Claramente, a questão de saber se um dado x é um composto é equivalente à questão de se x é um membro de COMPOSTO. Pode-se mostrar que COMPOSTO ∈ NP verificando se ele satisfaz a definição acima (se identificarmos os números naturais com suas representações binárias).

O COMPOSTO também está em P, fato demonstrado pela invenção do teste de primalidade AKS .

NP-completude

Existem muitas maneiras equivalentes de descrever NP-completude.

Seja L uma linguagem sobre um alfabeto finito Σ.

L é NP-completo se, e somente se, as duas condições a seguir forem satisfeitas:

1. L ∈ NP; e
2. qualquer L em NP é redutível no tempo polinomial para L (escrito como ), onde se, e somente se, as duas condições a seguir forem satisfeitas: ${\ displaystyle L '\ leq _ {p} L}$${\ displaystyle L '\ leq _ {p} L}$
   1. Existe f  : Σ * → Σ * tal que para todo w em Σ * temos: ; e${\ displaystyle (w \ in L '\ Leftrightarrow f (w) \ in L)}$
   2. existe uma máquina de Turing em tempo polinomial que para com f ( w ) em sua fita em qualquer entrada w .

Alternativamente, se L ∈ NP, e há outro problema NP-completo que pode ser reduzido em tempo polinomial para L , então L é NP-completo. Esta é uma maneira comum de provar que algum problema novo é NP-completo.

Cultura popular

O filme Caixeiro Viajante , do diretor Timothy Lanzone, é a história de quatro matemáticos contratados pelo governo dos Estados Unidos para resolver o problema P versus NP.

No sexto episódio da sétima temporada dos Simpsons " Treehouse of Horror VI ", a equação P = NP é vista logo após Homer acidentalmente tropeçar na "terceira dimensão".

No segundo episódio da 2ª temporada de Elementary , "Solve for X" gira em torno de Sherlock e Watson investigando os assassinatos de matemáticos que estavam tentando resolver P contra NP.

Veja também

• Complexidade do jogo
• Lista de problemas não resolvidos em matemática
• Conjectura de jogos únicos
• Problemas não resolvidos na ciência da computação

Notas

Referências

Fontes

• Rachel Crowell (28 de maio de 2021). "As principais questões não resolvidas em matemática permanecem principalmente misteriosas. Apenas um dos sete problemas do Prêmio do Milênio nomeados 21 anos atrás foi resolvido" . www. Scientificamerican.com . Página visitada em 21 de junho de 2021 . Esse problema diz respeito à questão de saber se as questões que são fáceis de verificar (uma classe de consultas chamada NP) também têm soluções que são fáceis de encontrar (uma classe chamada P).
• Hosch, William L (11 de agosto de 2009). "Matemática do problema P versus NP" . www. britannica.com (15 de março de 2012 Gregersen, Smith; revisado, atualizado) . Indiana University Northwest (blogs.britannica.com/author/whosch/page/3/) . Página visitada em 20 de junho de 2021 .Manutenção CS1: localização ( link )
• "Problema P vs NP" . www.claymath.org (Cook, Levin) . Página visitada em 20 de junho de 2021 . Suponha que você esteja organizando acomodações para um grupo de quatrocentos estudantes universitários. As vagas são limitadas e apenas cem alunos receberão vagas no dormitório. Para complicar as coisas, o Reitor forneceu a você uma lista de pares de alunos incompatíveis e solicitou que nenhum par dessa lista apareça em sua escolha final. Este é um exemplo do que os cientistas da computação chamam de problema NP ...

Leitura adicional

• Cormen, Thomas (2001). Introdução aos algoritmos . Cambridge: MIT Press . ISBN 978-0-262-03293-3.
• Garey, Michael; Johnson, David (1979). Computadores e intratabilidade: um guia para a teoria da NP-completude . São Francisco: WH Freeman and Company . ISBN 978-0-7167-1045-5.
• Goldreich, Oded (2010). P, NP e NP-Completude . Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. Rascunhos online
• Immerman, N. (1987). "Linguagens que capturam classes de complexidade". SIAM Journal on Computing . 16 (4): 760–778. CiteSeerX  10.1.1.75.3035 . doi : 10.1137 / 0216051 .
• Papadimitriou, Christos (1994). Complexidade computacional . Boston: Addison-Wesley. ISBN 978-0-201-53082-7.

links externos

• Fortnow, L .; Gasarch, W. "Computational complex " .
• De Aviad Rubinstein Dureza de aproximação entre P e NP , vencedor do ACM é 2017 Tese de Doutorado Award .
• "P vs. NP e o Zoológico da Complexidade Computacional" . 26 de agosto de 2014 - via YouTube .