## 3.2.2 ALGORITMOS DE VERIFICACIÓN

Podemos decir informalmente, que los algoritmos son procedimientos paso a paso para resolver problemas. Se puede pensar en ellos como simples programas de computadora, escritos en un lenguaje artificial específico.

Se dice que un algoritmo resuelve un problema A, si dicho algoritmo se puede aplicar a cualquier instancia I de A, y se garantiza que siempre produce una solución para dicha instancia. De manera general, nos interesa encontrar el algoritmo más eficiente para resolver cierto problema. En su sentido más amplio, la noción de eficiencia involucra a todos los recursos computacionales necesarios para la ejecución de un algoritmo.

Por algoritmo más eficiente usualmente nos referimos al más rápido. Debido a que los requerimientos de tiempo son usualmente un factor dominante cuando se trata de determinar si un algoritmo es lo suficientemente eficiente para ser útil en la práctica, nos concentraremos en este recurso.

Los científicos de la computación realizan la distinción entre algoritmos de tiempo polinómico y algoritmos de tiempo exponencial cuando se trata de caracterizar a los algoritmos como suficientemente eficiente y muy ineficiente respectivamente.

Un algoritmo de tiempo polinomial se define como aquel con función de complejidad temporal en O(p(n)) para alguna función polinómica p, donde n denota el tamaño de la entrada. Cualquier algoritmo cuya función de complejidad temporal no pueda ser acotada de esta manera, se denomina algoritmo de tiempo exponencial.

La mayoría de los algoritmos de tiempo exponencial son simples variaciones de una búsqueda exhaustiva, mientras que los algoritmos de tiempo polinomial, usualmente se obtienen mediante un análisis más profundo de la estructura del problema. En la teoría de la complejidad computacional, existe el consenso de que un problema no está "bien resuelto" hasta que se conozca un algoritmo de tiempo polinomial que lo resuelva. Por tanto, nos referiremos a un problema como intratable, si es tan difícil que no existe algoritmo de tiempo polinomial capaz de resolverlo.

###