P versus NP

O problema P versus NP é um dos problemas mais importantes e não resolvidos da ciência da computação.

Complexidade Computacional

A complexidade computacional é uma medida da dificuldade (em termos de tempo, memória ou algum outro critério) de executar um algoritmo.

Exemplo: Classificando uma lista. Usando o algoritmo Quicksort, a complexidade é n² em pior caso e n log(n) em média, onde n é o tamanho do array de entrada.

Exemplo: Encontrando um valor em uma lista não ordenada.

Média: (N+1)/2 comparações

Pior caso: N

O algoritmo de busca linear é um algoritmo O(n).

O que é P vs NP?

A classe P consiste em problemas cujas soluções podem ser ENCONTRADAS em tempo polinomial.
A classe NP consiste em problemas cujas soluções podem ser VERIFICADAS em tempo polinomial.

Em outras palavras, o tempo polinomial pode ser O(N²), O(N⁷) ou qualquer complexidade polinomial. A ideia por trás dessa classificação é que esses problemas são considerados "fáceis" no sentido de que podem ser resolvidos com as capacidades computacionais atuais.

Qual é a diferença entre encontrar uma solução e verificar uma solução?

Exemplo:

Para ENCONTRAR UMA SOLUÇÃO, precisaríamos testar se 4819 é divisível por 2, 3, 5, 7, 11, 13, 17—isto é, verificar quais números primos a dividem.

No entanto, o problema inverso é muito mais simples:

Com uma calculadora básica, podemos VERIFICAR que 79 × 61 = 4819.

Toda a criptografia RSA moderna é baseada nessa assimetria!

Um problema pode ser exponencialmente difícil de resolver, com complexidade O(2^N) ou O(N!), mas ainda assim ser fácil de verificar—o que significa que pertence à classe NP.

Uma máquina determinística refere-se a uma máquina de Turing, um modelo abstrato de computação. Uma máquina de Turing não determinística, por outro lado, se comporta como uma máquina de Turing regular, mas pode explorar um número infinito de ramificações em paralelo.

Em resumo:

• Classe P: Tempo polinomial – ENCONTRANDO a solução em tempo polinomial (P).

• Classe NP: Tempo Polinomial Não Determinístico – VERIFICANDO a solução em tempo polinomial (P).

(NP não significa "Não Polinomial" – não cometa esse erro!)

NP-Completo e NP-Difícil

Claramente, P está contido em NP—já que, se é possível encontrar uma solução, também é possível verificar se uma solução satisfaz o problema.

No entanto, no Complexity Zoo, existem algumas entidades a mais. Quais são elas?

NP-Completo e NP-Difícil

• NP-Completo – Esses são os problemas de decisão mais difíceis dentro da classe NP.

Um problema é NP-Completo se todo problema em NP pode ser convertido nele em tempo polinomial.

Exemplos: Problema do Caixeiro Viajante, Satisfatibilidade (SAT), Cobertura de Vértices, etc.
Veja Os 21 Problemas NP-Completo de Karp para mais exemplos.

Em outras palavras, imagine que temos um resolvedor eficiente (algoritmo de tempo polinomial) para o Problema do Caixeiro Viajante. Como todo problema NP pode ser transformado no Problema do Caixeiro Viajante, resolvê-lo de forma eficiente significaria que todos os problemas NP também poderiam ser resolvidos de forma eficiente. Se você resolver um problema NP-Completo, você resolve todos.

• NP-Difícil – Esses são problemas que são pelo menos tão difíceis quanto NP-Completo, mas não necessariamente têm soluções que podem ser verificadas em tempo polinomial.

Problemas de otimização que surgem na vida real, como otimização de colheitas ou planejamento florestal, muitas vezes envolvem variáveis lineares e inteiras com numerosas restrições—esses são tipicamente NP-Difíceis.

P = NP ou não?

A grande questão é se P = NP ou não. Pode parecer simples, mas até hoje, ninguém conseguiu provar ou refutar essa afirmação.

Há até um prêmio de 1 milhão de dólares para quem resolver a questão. É um dos sete Problemas do Milênio, promovido pelo Clay Mathematics Institute.

🔗 Problemas do Milênio – Clay Mathematics Institute

O Clay Institute foi inspirado pelos 23 problemas propostos pelo matemático David Hilbert em 1900, que, de uma forma ou de outra, guiou o desenvolvimento da matemática nas décadas seguintes.

Quanto ao Complexity Zoo, uma vez que resolver a questão principal (P vs NP) é difícil, os matemáticos se concentram em resolver problemas que podem ser abordados. Isso levou à criação de várias outras definições de tipos de complexidade computacional.

A Computação Quântica Resolve?

Quando novos paradigmas computacionais, como computação quântica, surgem, entender seu potencial ajuda a definir limites e expectativas.

No caso da computação quântica, acredita-se que seja mais poderosa do que a classe P, mas não capaz de resolver todos os problemas NP. Ela pode também ser capaz de resolver problemas além da classe NP.

Na verdade, apenas porque um problema é polinomial, não significa necessariamente que seja fácil. Um problema com complexidade O(N⁹⁹⁹⁹) ainda seria extremamente difícil de resolver.

Por outro lado, problemas NP-completos com pequenos tamanhos de entrada podem de fato ser resolvidos com o poder computacional atual. Na prática, resolvedores modernos tornaram problemas anteriormente intratáveis pelo menos minimamente solucionáveis para aplicações do mundo real. Graças aos avanços em hardware e software, é possível lidar com problemas NP-Difíceis, ao menos uma parte significativa deles.

Bem, em qualquer caso, há um prêmio de 1 milhão de dólares para quem estiver disposto a se aprofundar no assunto! Apenas não ganhe e rejeite o prêmio como Grigori Perelman fez (veja o link abaixo)!

🔗 O Homem Que Mereceu um Prêmio de 1 Milhão de Dólares—E O Rejeitou