P=np vcs sabem jemte
Soluções para a tarefa
O que diabos se esconde por trás da pergunta ‘P=NP?’, e por que parece ser tão importante para os programadores? É uma pergunta ainda sem resposta desde 1971, ano em que foi formulada, que tira do sério os programadores. Se a resposta for P≠NP, as coisas ficariam mais ou menos na mesma, mas se for P=NP, estão muitas coisas mudariam e não necessariamente para melhor.
“O problema com a matemática não são as crianças, mas a forma como é ensinada”
Quando políticos dos EUA decidiram que o valor de pi era 3,2
Solucionado o mistério dos círculos de fadas da Namíbia
Detetives matemáticos investigam fraudes na loteria
Boa parte das pessoas tende a pensar que os computadores podem resolver todos os problemas, e que os que não podem ser resolvidos hoje, o serão amanhã, porque sua potência de cálculo cresce continuamente. Os programadores sabem, por outro lado, que uma infinidade de problemas de cálculo não terá solução nunca (os chamados problemas indecidíveis), e que para outros problemas existem algoritmos que os resolvem, mas utilizando para isso tanto tempo de cálculo que para efeitos práticos é como se fossem irresolúveis (os chamamos problemas intratáveis). Os problemas que são resolvidos pelos computadores em um tempo razoável são chamados de polinomiais, e todos eles se agrupam na chamada classe P. São chamados assim porque seu tempo de cálculo é descrito por um polinômio no tamanho dos dados. Por exemplo, o problema de multiplicar duas matrizes de n fileiras e colunas pode ser resolvido utilizando menos de n3 multiplicações. Nenhum dos problemas intratáveis está na classe P.
Existe outra classe de problemas, a que chamamos de NP, cuja definição está dada de tal maneira que inclui todos os problemas da classe P, mas também muitos outros que se comportam de maneira intrigante. Um desses problemas é o chamado problema do representante comercial: dado um mapa de estradas, consiste em encontrar o caminho mais curto para se visitar n cidades de uma só vez e voltar ao ponto de origem. Para esses novos problemas da classe NP, os melhores algoritmos conhecidos têm um tempo de trabalho parecido ao dos problemas intratáveis, mas ninguém conseguiu demonstrar que não existem algoritmos polinomiais para eles. Ninguém conseguiu demonstrar também que são intratáveis. Estão, por assim dizer, em uma espécie de limbo informático: não se sabe se são polinomiais ou se são intratáveis. A teoria desenvolvida nos últimos anos chegou, entretanto, a alguma conclusão útil: definiu uma subclasse da classe NP, a subclasse dos problemas NP-completos, na qual são agrupados os problemas mais difíceis da classe NP, de tal forma que, se para qualquer um dos tais problemas se encontrar um algoritmo polinomial, então todos eles seriam resolvidos em tempo polinomial e, além disso, a classe NP seria rebaixada a P, ou seja, teríamos a igualdade P=NP. E mais, se fosse demonstrado que um só dos problemas NP-completos é intratável, então todos eles o seriam e teríamos a desigualdade P≠NP.
Bons estudos.
FONTE: brasil.elpais