jdact
«Tudo isto pode parecer trivial, mas tem aplicações em muitas áreas fundamentais, como a feitura de horários em grandes escolas, a organização de conferências ou a planificação de voos de uma companhia aérea. Está na base de um novo ramo da matemática conhecido como complexidade computacional. Quando estes problemas eram solucionados manualmente, um a um, era difícil estudar muitas das suas características. A partir do momento em que passaram a poder ser resolvidos em computador, procurou-se estudar a complexidade dos processos de solução, os tais algoritmos, e começou-se a estimar o tempo que um computador leva a resolvê-los.
Em 1959, Richard Karp, então um jovem matemático com 24 anos de idade, acabado de se doutorar em Harvard, começou a trabalhar no centro de investigação da IBM e foi encarregado de procurar um processo automático de desenho de circuitos com um mínimo de transístores. Traduzido num programa de computador, o algoritmo limitava-se a explorar todos os circuitos possíveis e a calcular o seu custo. Mais tarde, em 1985, ao receber o prestigiado prémio Turing, Karp recordaria que essa abordagem parecia simples, mas tinha uma falha fundamental:
- «À medida que o número de variáveis aumentava, o número de circuitos que o Programa tinha de estudar crescia a um ritmo vertiginoso e, consequentemente, nunca pudemos avançar para além da solução de problemas infantis».
Cortesia de questaodosuniversais
Karp, que passaria ainda uma década na IBM antes de se tornar professor em Caltech, o célebre California Institute of Technology em Pesadena, tinha verificado directamente um fenómeno que veio a ocupar centenas de investigadores e a originar milhares de estudos: os problemas podem ser simples e as técnicas fáceis de aplicar, mas podem tornar-se rapidamente impossíveis de tratar, mesmo com os computadores mais poderosos. Nas décadas seguintes, matemáticos, lógicos e especialistas em ciências da computação procuraram algoritmos mais eficazes, mas chegaram sempre ao mesmo resultado: há problemas que são facilmente resolúveis, e cuja complexidade aumenta de forma controlada, e há problemas que rapidamente se tornam impossíveis de resolver, pois a sua complexidade cresce exponencialmente com o número de variáveis e restrições.
Actualmente distinguem-se os chamados problemas de tipo R em que a complexidade aumenta de forma polinomial com o aumento de variáveis, e os problemas de tipo NP-completo, não determinístico polinomial, em que apenas se conhecem algoritmos que necessitam de um tempo crescente de forma mais que polinomial, portanto incomportável quando o número de variáveis aumenta.
Cortesia de gratuito
Não se sabe ainda se os problemas tipo NP-completo, que são formalmente redutíveis uns aos outros, são passíveis de abordagem mais simples, tipo P. Esta questão foi abordada há 15 anos por Karp, na altura em que recebeu o prémio Turing, mas continua a ser o grande problema em aberto das ciências da computação. Os especialistas assumem que se trata de dois tipos diferentes e irredutíveis de problemas, mas ainda não o conseguiram demonstrar.
O nosso jantar de anos, que era um problema 2-SAI, era de tipo P. Se em vez de termos de escolher três amigos de entre cinco, tivermos de escolher 30 de entre 50, um programa de computador pode encontrar rapidamente uma solução. E, se formos secretários das Nações Unidas e tivermos de escolher 300 pessoas de um grupo de 500, o computador pode espernear um pouco mais, e acabar por encontrar uma resposta, ou mostrar-nos que não há solução possível, o que é igualmente importante.
Estranhamente, se passarmos a um problema 3-SAT, em que há restrições da forma «ou o António e a Beatriz ou o Carlos de fora», entramos num mundo diferente. Cruzamos a fronteira entre os problemas de tipo P, em que acabaremos por encontrar uma solução, para problemas de tipo NP-completo, em que basta termos umas dezenas de amigos para não haver computador no mundo que nos permita jantar a tempo e horas». In Nuno Crato, A Matemática das Coisas, Gradiva, Sociedade Portuguesa de Matemática, Abril 2008, ISBN 978-989-616-241-2.
Cortesia de Gradiva/JDACT
