P versus NP
Origem: Wikipédia, a enciclopédia livre.
O Problema "P versus NP" é de enorme relevância em campos que vão desde a Engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via Internet.
Índice |
[editar] Definição do problema
Esse problema, incidentalmente, tem uma formulação fácil de ser entendida. De modo simplificado, ele pergunta se existem problemas matemáticos cuja resposta pode ser verificada em tempo prático (por exemplo, em tempo polinomial), MAS que não podem ser resolvidos (diretamente, sem se ter um candidato à solução) em tempo prático. Ilustrando: se alguém lhe disser que o número 13.717.421 pode ser escrito como o produto de dois outros inteiros, você provavelmente demorará para provar isso; contudo, se lhe assoprarem que ele é o produto de 3.607 por 3.803, você seria capaz de muito rapidamente verificar tal fato.
O problema "P versus NP" parte da constatação que são muito frequentes as situações em que parece ser muito mais rápido verificar solução do que achar um processo de resolução, e então pergunta: isso sempre ocorre, ou simplesmente ainda não descobrimos um modo de resolvê-los rapidamente?
Para uma discussão mais desenvolvida, mas ainda evitando tecnicalidades, sobre o Problema "P versus NP", veja outro problema clássico: o problema do caixeiro viajante.
Não se iluda com a aparência de brincadeira deste problema. Ele NÃO é mais uma curiosidade inconsequente para entreter alunos desmotivados. Em verdade, ele é um problema que deve fazer parte da bagagem de todo profissional competente da área matemática. Sua importância resume-se em duas capacidades:
- de modo simples e concreto, exemplifica a enorme velocidade de crescimento da fatorial;
- prova-se que muitos problemas combinatórios envolvem tantas alternativas de solução quanto este problema, de modo que ele é uma espécie de "metro" com o qual medimos a complexidade computacional dos problemas combinatórios ocorrendo em engenharia e no trabalho científico.
[editar] Formulando o problema do caixeiro viajante
Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra. O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.
[editar] Exemplificando o caso n = 4
Se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve considerar poderia ser: saia de A e daí vá para B, dessa vá para C, e daí vá para D e então volte a A. Quais são as outras possibilidades? É muito fácil ver que existem seis rotas possíveis:
ABCDA
ABDCA
ACBDA
ACDBA
ADBCA
ADCBA
[editar] Complexidade computacional do problema
O problema do caixeiro é um clássico exemplo de problema de otimização combinatória. A primeira coisa que podemos pensar para resolver esse tipo de problema é reduzi-lo a um problema de enumeração: achamos todas as rotas possíveis e, usando um computador, calculamos o comprimento de cada uma delas e então vemos qual a menor. É claro que se acharmos todas as rotas estaremos contando-as, daí podermos dizer que estamos reduzindo o problema de otimização a um de enumeração.
Para acharmos o número R(n) de rotas para o caso de n cidades, basta fazer um raciocínio combinatório simples e clássico. Por exemplo, no caso de n = 4 cidades, a primeira e última posição são fixas, de modo que elas não afetam o cálculo; na segunda posição podemos colocar qualquer uma das 3 cidades restantes B, C e D, e uma vez escolhida uma delas, podemos colocar qualquer uma das 2 restantes na terceira posição; na quarta posição não teríamos nenhuma escolha, pois sobrou apenas uma cidade; consequentemente, o número de rotas é 3 × 2 × 1 = 6, resultado que tinhamos obtido antes contando diretamente a lista de rotas acima. De modo semelhante, para o caso de n cidades, como a primeira é fixa, o leitor não terá nenhuma dificuldade em ver que o número total de escolhas que podemos fazer é (n-1) × (n-2) × ... × 2 × 1. De modo que, usando a notação de fatorial: R(n) = (n - 1)!.
Assim que nossa estratégia reducionista consiste em gerar cada uma dessas R(n) = (n - 1)! rotas, calcular o comprimento total das viagens de cada rota e ver qual delas tem o menor comprimento total. Trabalho fácil para o computador, diria alguém. Bem, talvez não. Vejamos o porquê.
Suponhamos que temos um muito veloz computador, capaz de fazer 1 bilhão de adições por segundo. Isso parece uma velocidade imensa, capaz de tudo. Com efeito, no caso de 20 cidades, o computador precisa apenas de 19 adições para dizer qual o comprimento de uma rota e então será capaz de calcular 109 / 19 = 53 milhões de rotas por segundo. Contudo, essa imensa velocidade é um nada frente à imensidão do número 19! de rotas que precisará examinar. Com efeito, acredite se puder, o valor de 19! é 121.645.100.408.832.000 (ou , aproximadamente, 1,2 × 1017 em notação científica). Consequentemente, ele precisará de 1,2 × 1017 / (53 × 106) = 2,3 × 109 segundos para completar sua tarefa, o que equivale a cerca de 73 anos. O problema é que a quantidade (n - 1)! cresce com uma velocidade alarmante, sendo que muito rapidamente o computador torna-se incapaz de executar o que lhe pedimos. Constate isso mais claramente na tabela a seguir:
| n | rotas por segundo | (n - 1)! | cálculo total |
|---|---|---|---|
| 5 | 250 milhões | 24 | insignificante |
| 10 | 110 milhões | 362.880 | 0.003 seg |
| 15 | 71 milhões | 87 bilhões | 20 minutos |
| 20 | 53 milhões | 1,2 × 1017 | 73 anos |
| 25 | 42 milhões | 6,2 × 1023 | 470 milhões de anos |
Observe que o aumento no valor do n provoca uma muito lenta diminuição na velocidade com que o computador calcula o tempo de cada rota (ela diminui apenas de um sexto ao n aumentar de 5 para 25), mas provoca um imensamente grande aumento no tempo total de cálculo. Em outras palavras: a inviabilidade computacional é devida à presença da fatorial na medida do esforço computacional do método da redução. Com efeito, se essa complexidade fosse expressa em termos de um polinómio em n o nosso computador seria perfeitamente capaz de suportar o aumento do n. Confira isso na seguinte tabela que corresponde a um esforço computacional polinomial R(n) = n5:
| n | rotas por segundo | n5 | cálculo total |
|---|---|---|---|
| 5 | 250 milhões | 3.125 | insignificante |
| 10 | 110 milhões | 100.000 | insignificante |
| 15 | 71 milhões | 759.375 | 0,01 seg |
| 20 | 53 milhões | 3.200.000 | 0,06 seg |
| 25 | 42 milhões | 9.765.625 | 0,23 seg |
Então o método reducionista não é prático (a não ser para o caso de muito poucas cidades), mas será que não se pode inventar algum método prático (por exemplo, envolvendo esforço polinomial na variável número de) para resolver o problema do caixeiro viajante? Bem, apesar de inúmeros esforços, ainda não foi achado tal método e começa-se a achar que o mesmo não existe.
[editar] Conclusão
A existência ou não de um método polinomial para resolver o problema do caixeiro viajante é um dos grandes problemas em aberto da Matemática na medida em que Steven Cook (1971) e Richard Karp (1972) mostraram que uma grande quantidade de problemas importantes (como é o caso de muitos tipos de problemas de otimização combinatória, o caso do problema da decifragem de senhas criptografadas com processos modernos como o DES, etc.) podem ser reduzidos, em tempo polinomial, ao problema do caixeiro.
Consequentemente: se descobrirmos como resolver o problema do caixeiro em tempo polinomial ficaremos sendo capazes de resolver, também em tempo polinomial, uma grande quantidade de outros problemas matemáticos importantes; por outro lado, se um dia alguém provar que é impossível resolver o problema do caixeiro em tempo polinomial no número de cidades, também se terá estabelecido que uma grande quantidade de problemas importantes não tem solução prática. Por isso, já foi até oferecido um Prêmio de um milhão de dólares a quem conseguir resolver este problema matemático.
Costuma-se resumir essas propriedades do problema do caixeiro viajante dizendo que ele pertence à categoria dos problemas NP-completo.
[editar] Ver também
- Estrutra de dados árvore ordenada - DAGs, árvores binárias e outras formas especiais de grafos.
- Teoria da computação
- Grafo (estrutura de dados)
- Lista de tópicos da teoria dos grafos
- Construção de grafos
- Redes Complexas
