LostBrasil :: Exibir tópico

doug.manoel

p=np. será?

a complexidade computacional de um problema é, em última análise, o tempo que se gasta, no pior caso, para resolvê-lo. problemas computacionais são resolvidos em computadores, usando algoritmos, que são seqüências de instruções bem definidas, que o computador [qualquer que seja] pode executar de forma precisa. por trás deste blog, há um conjunto de algoritmos, sendo executados por servidores no terra.com.br, para transformar os tecles e clicks do leitor em páginas visualizadas na tela.

algoritmos estão, na verdade, por trás de quase tudo o que acontece no mundo. o motor flex depende de algoritmos para analisar o resultado da compbustão e sintonizar o motor para a mistura de combustível que está no tanque. seu banco -on e off line- é uma montanha de algoritmos. assim como o sistema de saúde, o imposto de renda, a tv digital... o voar dos aviões, o sistema de controle de tráfego aéreo e por aí vai. não, os pássaros ainda não são informatizados e seu voar é livre. por enquanto.

pois bem. os problemas computacionais do tipo P são aqueles em que o tempo [ou o custo] para tratar uma instância qualquer do problema é, no máximo, de ordem polinomial. algo como o tamanho do problema elevado ao quadrado, por exemplo. ou o tamanho do problema multiplicado pelo logaritmo dele mesmo, que vem a ser a complexidade de ordenar um arquivo qualquer [ou de começar com uma lista desordenada de palavras e deixá-la, ao fim do algoritmo, ordenada].

há problemas cuja complexidade de solução depende de uma função não polinomial do tamanho da entrada, como seu fatorial [n! = 1* 2 * 3 * ... * n]. gerar todas as permutações de um conjunto de N números gasta tempo N!, onde exclamação, aí atrás, é o símbolo para fatorial. que vem a ser uma função que cresce muito depressa. quer ver? se um problema tem complexidade fatorial e seu tamanho é 3 [três objetos como entrada...], o custo de resolvê-lo é 6 [pois 1 * 2 * 3 = 6]. tamanho 4 custa 24, 5 custa 120, 6 custa 720, 7 já vai pra 5040... e, se o problema for de tamanho 20, o custo é nada menos do que 2.432.902.008.176.640.000! quase dois e meio quintilhões. coisa de louco. isso faz com que problemas para os quais não se conhece uma solução polinomial sejam, via de regra, considerados computacionalmente intratáveis.

até aqui, dá pra entender o que são os problemas do tipo P: aqueles para os quais -mesmo em seu pior caso- a solução tem custo polinomial. e o NP, lá do título? NP é a classe problemas considerados computacionalmente "razoáveis", aqueles para os quais, dada uma possível solução, pode-se testá-la em tempo polinomial. ou seja, para os quais, se conseguirmos uma potencial solução de forma não determinística, temos um algoritmo lá da classe P que diz se a solução é verdeira ou não. talvez venha, daí, o nome da classe: N de "não determinístico" e P de polinomial. para mais detalhes sobre o assunto, de forma tão simples quanto é possível no caso, leia esta explicação do professor paulo feofiloff.

juntando as duas coisas, chegamos ao título do texto de hoje: será que há uma solução polinomial para todos os problemas computacionalmente razoáveis? será que, para cada e todo problema não determinístico polinomial [NP] eu consigo achar uma solução polinomial [em P]? ou seja, será que consigo provar que P=NP, que a classe dos problemas "razoáveis" tem complexidade polinomial, encerrando uma discussão iniciada em 1971 [por cook, veja aqui] e ganhando um prêmio de um milhão de dólares do clay institute? e isso contra a opinião da vasta maioria dos cientistas da área? em pesquisa recente, apenas 9 entre 100 cientistas que estão trabalhando no problema disseram acreditar que P=NP. e apenas 5 entre os 100 disseram que o problema seria resolvido -de uma forma ou de outra- antes de 2010.

se P=NP, haverá conseqüências muito interessantes do ponto de vista de [entre muitas outras áreas] logística, biologia, possivelmente criptografia e, talvez, toda a matemática. porque provar teoremas se tornaria muito mais fácil, segundo o próprio cook, o cientista que começou a discussão: ...it [P=NP] would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time... em suma, parte da computação e matemática que está sendo feita e usada hoje pode mudar consideravelmente, com a provável inclusão, na lista, dos sistemas de segurança das transações financeiras. vai ser um auê federal. mundial, aliás.

sim. e daí? o leitor acorda na segunda e, primeira coisa que lê é este blog, com esta conversa mole e complicada sobre obscuridades matemáticas e computacionais quase ininteligíveis... o que é que o autor tá pensando? que isso aqui é aula de teoria da computação? não. este texto está aqui por duas razões. primeira: se P=NP, nossas vidas vão mesmo mudar. pode acreditar. segunda: um brasileiro [e trabalhando no brasil], sóstenes lins, professor titular do departamento de matemática da ufpe, anunciou em seminário recente, em recife, estar finalizando os detalhes de uma prova definitiva de que, sim, P=NP. agora é esperar pra ver os detalhes. boa sorte, sóstenes.

Fonte: Blog Silvio Meira - Terra Magazine

Pelo menos um terço do que se estuda na área da computação será revisto depois disso se confirmar.

Se esse professor publicar esse material e em 2 anos ninguém peitar e provar que ele tá errado, ele será quase um Deus. 1 milhão de dólares será o primeiro de muitos premios dele caso isso aconteça.

E tomara que isso se confirme, o Brasil merece um prêmio desse. Very Happy