O problema P versus NP é um dos problemas mais importantes e não resolvidos da ciência da computação.
Motivação para escrever este tutorial: participei de uma palestra sobre Advanced Planning & Scheduling, só que o apresentador falou uma série de bobagens sobre este tema… se fosse só detalhes técnicos simplificados para leigos entenderem, ok, mas no caso, a pessoa claramente não dominava o assunto a que se propôs a palestrar.
Complexidade computacional
A complexidade computacional é uma medida da dificuldade (em tempo, memória, algum outro critério) para rodar um algoritmo.
Exemplo: Ordenar uma lista. Pelo algoritmo Quicksort, temos a complexidade n^2 no pior caso, e n log(n) na média, onde n é o tamanho do vetor de entrada.
Exemplo: Encontrar um valor numa 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 é de problemas cuja solução pode ser ENCONTRADA em tempo polinomial.
E a NP, são problemas cuja solução pode ser VERIFICADA em tempo polinomial.
Ou seja, o polinomial pode ser O(N²), O(N⁷), qualquer polinômio. A noção por trás disso é que são problemas “fáceis”, possíveis de serem resolvidos com a capacidade computacional atual.
Qual a diferença entre encontrar uma solução e verificar uma solução?
Exemplo:
Fatore 4819 em multiplicação de números primos.
Para ENCONTRAR UMA SOLUÇÃO, teríamos que testar a divisão de 4819 por 2, 3, 5, 7, 11, 13, 17; ou seja, por quais números primos o valor é divisível.
Já o problema inverso é muito mais simples:
Verifique que 79 * 61 = 4819
Basta uma calculadora simples de bolso para VERIFICAR que 79*61 = 4819.
Toda a criptografia RSA atual está baseada nesta assimetria!
Um problema pode ser exponencialmente difícil de resolver, da ordem O(2^N) , O(N!), mas mesmo assim, ser muito fácil de ter uma solução verificada – e daí estará na classe NP.
Definição da Wikipedia
P consiste em todos os problemas de decisão que podem ser resolvidos por uma máquina determinística sequencial em uma quantidade de tempo que é polinomial para o tamanho da entrada;
NP consiste em todos os problemas de decisão cujas soluções positivas podem ser verificadas em tempo polinomial dada a informação correta, ou de forma análoga, cujas soluções podem ser encontradas em tempo polinomial em uma máquina não determinística.
A máquina determinística citada é uma máquina de Turing, um modelo abstrato de computador. Já uma máquina de Turing não determinística é como se fosse uma máquina de Turing simples, porém capaz de criar inúmeros branchs em paralelo, infinitamente.
Em resumo:
Classe P: Polinomial time – RESOLVER a solução em tempo polinomial (P)
Classe NP: Non Deterministic Polinomial time – VERIFICAR a solução em tempo polinomial (P)
(NP não significa “Não Polinomial” – não cometa esta barbaridade)
NP-Complete e NP-Hard
Claramente, P está contido em NP – já que é possível encontrar a solução, também é possível verificar se uma solução atende o problema.
Porém, no Zoológico da Complexidade, temos alguns entes a mais. O que são?
NP Complete – são os problemas de decisão mais difíceis da classe NP.
Um problema é NP-complete se todo problema da classe NP pode ser convertido para ele, em tempo polinomial.
Exemplos: caixeiro-viajante, satisfiability, vertex cover, …
Vide https://pt.wikipedia.org/wiki/21_problemas_NP-completos_de_Karp para outros exemplos.
Ou seja, imagine que eu tenha um solver eficiente, em tempo polinomial, para o problema do caixeiro-viajante. Se todo problema NP pode ser convertido para o problema do caixeiro-viajante, e este tiver solução, então todos os problemas NP serão resolvíveis de forma eficiente. Se resolver um NP-Complete, resolve todos.
NP Hard – Problemas ao menos NP-Complete, mas que não precisam ser verificados polinomialmente.
Problemas de otimização que encontramos no dia a dia, na prática, como a otimização de colheita ou de silvicultura, envolvem variáveis lineares e inteiras e inúmeras restrições, são normalmente NP-Hard.
Seria P = NP ou não?
A grande questão colocada é se P = NP ou não. Pode parecer fácil, mas até hoje ninguém nunca conseguiu provar ou desprovar a afirmação.
Há até um prêmio de US$ 1 milhão para quem resolver a questão. É um dos 7 problemas do milênio, promovido pelo Instituto Clay.
https://www.claymath.org/millennium-problems
Por sua vez, o Instituto Clay se inspirou nos 23 problemas que o matemático David Hilbert propôs, em 1900 e que, de uma forma ou outra, guiou o desenvolvimento da matemática pelas décadas seguintes.
Sobre o zoo da complexidade, já que é difícil resolver a questão principal, os matemáticos resolvem os problemas possíveis de serem resolvidos, daí existirem diversas outras definições de tipos de complexidade computacional.
Quando surgem novos paradigmas de computação, como a quântica, ter a visão do que ela possivelmente pode atingir ajuda a entender os limites e expectativas. No caso da computação quântica, suspeita-se que ela seja mais abrangente que a classe P, porém não resolva a NP, podendo resolver também problemas fora da classe NP.
Na verdade, um problema ser polinomial não quer dizer necessariamente ser fácil. Um problema de O(N⁹⁹⁹⁹) vai ser extremamente complicado de resolver.
O inverso, problemas NP-completo, com tamanho pequeno, são sim resolvíveis com a computação atual. Na prática, os solvers do mundo atual tornaram problemas intratáveis minimamente rodáveis para problemas do dia a dia. Devido ao desenvolvimento de hardware e software, é possível conviver com problemas NP-Hard, pelo menos boa parte deles.
Bom, de qualquer forma, tem um prêmio de US$ 1 milhão para quem quiser se aventurar e entrar de cabeça no tema! Só não vá ganhar e recusar, como fez Grigori Perelman (vide link abaixo)!
Veja também:
ideiasesquecidas.com 