## 3.1 TIEMPO POLINOMIAL

Luego de presentar las técnicas y estrategias de algoritmos, volvemos la atención a la complejidad de los problemas. Se observa que hay problemas fáciles y problemas difíciles.

Un problema es fácil si puede resolverse mediante un algoritmo eficiente, tal vez un algoritmo con complejidad temporal polinomial. Al revés, si un problema no puede resolverse con ningún algoritmo con complejidad temporal polinomial, entonces debe tratarse de un problema difícil. Por lo general, dado un problema, si ya se sabe que existe un algoritmo que resuelve el problema en tiempo polinomial, se tiene la certeza de que es un problema fácil. No obstante, si no se ha encontrado ningún algoritmo polinomial que resuelva el problema, difícilmente puede concluirse que jamás podrá encontrarse alguno con complejidad temporal polinomial que resuelva el problema.

Por fortuna, existe una teoría de algoritmos NP-completos que puede aplicarse para medir la complejidad de un problema. Si se demuestra que un problema es NP-completo, entonces se considerará como un problema difícil y la probabilidad de encontrar un algoritmo de tiempo polinomial para resolver el problema es bastante pequeña. Resulta interesante observar aquí que existe una multitud de problemas que no parecen difíciles, pero que en realidad son problemas NP-completos.

###