O senhor já ouviu um engenheiro de software se referir a um problema como “NP-completo”? Esse é um jargão sofisticado da ciência da computação abreviação de “incrivelmente difícil”:
A característica mais notável dos problemas NP-completos é que não se conhece nenhuma solução rápida para eles, ou seja, o tempo necessário para resolver o problema usando qualquer algoritmo conhecido atualmente aumenta muito rapidamente à medida que o tamanho do problema cresce. Como resultado, o tempo necessário para resolver até mesmo versões moderadamente grandes de muitos desses problemas chega facilmente à casa dos bilhões ou trilhões de anosusando qualquer quantidade de poder de computação disponível atualmente. Consequentemente, determinar se é possível ou não resolver esses problemas rapidamente é um dos principais problemas não resolvidos na Ciência da Computação atualmente.
Embora ainda não tenha sido descoberto um método para calcular as soluções de problemas NP-completos usando um tempo razoável, os cientistas da computação e programadores ainda encontram problemas NP-completos com frequência. Um programador experiente deve ser capaz de reconhecer um problema NP-completo para que não perca tempo inadvertidamente tentando resolver um problema que, até o momento, tem escapado a gerações de cientistas da computação.
O senhor quer ser um especialista programador, o senhor não acha? É claro que o senhor sabe!
Problemas NP-completos são como pornografia hardcore. Ninguém consegue definir o que torna um problema NP-completo, exatamente, mas o o senhor saberá quando o vir. Só desta vez, vou me abster de minha prática habitual de inserir imagens para ilustrar meu argumento.
(Atualizar: Eu estava tentando fazer uma alusão poética ao problema P=NP aqui, mas com base nos comentários, isso é confuso e possivelmente incorreto. Por isso, vou suprimir essa frase. Em vez disso, indico ao senhor esta pesquisa P=NP (pdf); leia os comentários dos professores de Ciências da Computação (incluindo Knuth) para ter uma ideia de como isso pode ser realista).
Em vez disso, vou recomendar um livro que Anthony Scian me recomendou: Computers and Intractability: A Guide to the Theory of NP-Completeness (Um guia para a teoria da NP-Completude).
Como todos os livros de engenharia de software que recomendo, este livro tem uma qualidade atemporal. Ele foi publicado originalmente em 1979, um testemunho brilhante de pessoas inteligentes que enfrentam problemas realmente difíceis na ciência da computação: “Não consigo encontrar um algoritmo eficiente, mas todas essas pessoas famosas também não conseguem.”
Então, quantos problemas são NP-completos? Muitos.
Mesmo que o senhor seja um leigo, já deve ter experimentado a NP-Completude na forma de Minesweeper, como Ian Stewart explica. Mas, para os programadores, eu diria que o problema de NP-completude mais conhecido é o problema do problema do caixeiro viajante.
Considerando um número de cidades e os custos de viagem de qualquer cidade para qualquer outra cidade, qual é a rota de ida e volta de menor custo que visita cada cidade exatamente uma vez e depois retorna à cidade de partida?
O solução de força bruta — tentando todas as permutações possíveis entre as cidades, pode funcionar para uma rede muito pequena de cidades, mas rapidamente se torna insustentável. Mesmo se usássemos CPUs teóricas que nossos filhos possam ter ou os filhos de nossos filhos. E o que é pior, todos os outros algoritmos que criamos para encontrar um caminho ideal para o vendedor têm o mesmo problema. Essa é a característica comum dos problemas NP-completos: eles são exercícios de heurística e aproximação, conforme ilustrado por este desenho animado do xkcd:
O que o especialista o que os programadores fazem quando se deparam com um problema intratável? Eles trapaceiam. E o senhor também deveria! De fato, alguns dos aproximações modernas para o Problema do Caixeiro Viajante são notavelmente eficaz.
Foram desenvolvidos vários algoritmos de aproximação que produzem rapidamente boas soluções com alta probabilidade. Os métodos modernos podem encontrar soluções para problemas extremamente grandes (milhões de cidades) em um tempo razoável, com uma alta probabilidade de estar a apenas 2-3% de distância da solução ideal.
Infelizmente, nem todos os problemas NP-completos têm boas aproximações. Mas para aqueles que têm, eu me pergunto: se podemos chegar tão perto de uma solução ótima trapaceando, será que realmente importa se não há um algoritmo conhecido para produzir o solução ótima? Se eu não aprendi mais nada com os problemas NP-completos, aprendi isso: Às vezes, inventar truques inteligentes pode ser mais interessante do que procurar em vão a solução perfeita.
Considere o seguinte Primeiro ajuste decrescente para o algoritmo NP-completo Problema de empacotamento de caixas . Ele não é perfeito, mas é incrivelmente simples e rápido. O algoritmo é tão simples que, na verdade, é demonstrado regularmente em seminários de gerenciamento de tempo. O senhor, e ele garante que o senhor sempre chegará a 22% da solução perfeita. Nada mal para um péssimo cheat.
Então, o que é o senhor favorito em NP-completo?