Teoria da Complexidade e o Caixeiro Viajante

Resumo: Introduc¸ ˜ao a Teoria da Complexidade de modo a apresentar o porque os profissionais se preocupam tanto com esse estudo e explicar o problema do Caixeiro Viajante(NP).
Abstract: Introduction to Theory Complexity to explain why the professionall worried so much about this study and explain the problem of NP algorithms.
A Teoria da Complexidade ela estuda a eficiˆencia dos algoritmos de modo a calcular qual seria o melhor modo de faze-lo, ou seja, otimizar esse algoritmo para que ele se torne mais rapido ou que ocupe menos espac¸o de mem´oria. Um problema enfrentado ´e que para essa otimizac¸ ˜ao acontecer ela depende de v´arios fatores da maquina a ser utilizada, como o hardware, software, mem´oria dispon´ıvel, sistema operacional dentre outros. E para piorar a situac¸ ˜ao existe inumeras maquinas diferentes e um programa ´e feito para rodar em diferentes tipo de maquinas, portanto calcular qual a melhor maneira de se fazer um algoritmo n˜ao ´e t˜ao facil.
Outro problema ´e que existem algoritmos que nem se quer o homem chegou na soluc¸ ˜ao, porque para compilar tais programas demora-se milhares de anos, e um exemplo de algoritmos como esse ´e o do Caixeiro
Viajante, que ´e um problema matem´atico aparentemente simples mais sua estrutura ´e de crescimento fatorial. O problema acontece com um carteiro que vai de cidade em cidade e vocˆe tem que calcular a menor rota. Por´em o algoritmo precisa andar de rota por rota para calcular qual ´e menor, ou seja, se torna um problema de enumerac¸ ˜ao, como o crescimento ´e fatorial, n(numero de rotas) ´e elevad´ıssimo, fazendo com que a maquina mais rapida inventada at´e hoje demore milhares de