En la vida real existen muchos problemas prácticos para los cuales no se conoce ningún
algoritmo eficiente, pero cuya dificultad intrínseca no ha conseguido demostrar
nadie. Planteado un problema se necesita un algoritmo que ayude a resolverlo, pero no
cualquiera, se necesita encontrar el algoritmo más eficiente para su solución.
Generalmente la eficiencia del algoritmo se traduce en la rapidez del mismo, ya que el
tiempo requerido para encontrar la solución es a menudo uno de los factores
fundamentales para decidir si el mismo es eficiente o no eficiente.
Matemáticamente, los problemas pueden caracterizarse atendiendo a la dificultad que
entraña su resolución por un ordenador. Se han definido varias clases de problemas, entre
las que destacan las clases NP,NP-completo y NP-duro.
Se dice que un problema se puede resolver en un tiempo polinómico cuando el tiempo de
ejecución de un algoritmo que lo resuelve se puede relacionar con el tamaño de la entrada
con una fórmula polinómica. Los problemas para los que existe un algoritmo polinómico se
denominan P. Los problemas NP, son problemas para los que no se ha determinado una
solución polinomial factible. Esto no significa que la solución no exista, sino únicamente que
no se ha encontrado hasta el momento, o que la respuesta se obtendría con una cantidad
de recursos demasiado alta.
En otras palabras, la clase NP contiene los problemas cuya solución se verifica en tiempo
polinómico. Este es el tipo de problemas en los que no podemos evitar la fuerza bruta para
su resolución y no se conocen algoritmos que los resuelvan en tiempo polinómico.
Una gran cantidad de problemas útiles en el ámbito de la optimización combinatoria son
difíciles de resolver. Hay problemas que, pese a que no se haya encontrado un algoritmo polinómico que lo resuelva, si que se puede saber en tiempo polinómico si un valor
corresponde a la solución del problema. Por ejemplo, el cálculo de la raíz cuadrada de un
número puede ser un problema complicado. En cambio, saber si un determinado valor es
la raíz cuadrada de otro es bastante sencillo, ya que basta con elevar ese número al
cuadrado. A simple vista puede parecer que la gran mayoría de los problemas son NP, ya
que intuitivamente parece que comprobar una solución es bastante más sencillo que
calcularla. Sin embargo, para los problemas de optimización, comprobar si esos valores
corresponden a la solución óptima no es nada sencillo. De hecho, existen problemas que
requieren ejecutar el mismo algoritmo para buscar soluciones al problema como para
comprobar que unos de los valores son solución.
Los problemas P también son problemas NP, ya que siempre es posible comprobar que un
valor es solución al problema en tiempo polinómico. Si no se encuentra una forma más
sencilla de hacerlo, siempre se puede ejecutar el propio algoritmo polinómico que lo
resuelve y comprobar el resultado con el valor obtenido. Por tanto, el conjunto de
problemas P es un subconjunto de los problemas NP.
La teoría de la NP- completitud estudia la noción de propiedades verificables
polinomicamente. Intuitivamente, un problema de desición X es verificable eficientemente
si un ser omnisciente pudiera producir una evidencia convincente de que x∈X siempre
que asì fuera. Dada esta evidencia, se debería ser capaz de verificar eficientemente
que en verdad x∈X sin más contacto con el mencionado ser.
Referencias
Brassard, G., & Bratley, P. (2000). Fundamentos de Algoritmia. Prentice Hall.
Reina, G. V., & García, E. M. (2004). Sistemas evolutivos y selección de
indicadores. Universidad de Sevilla.
Muñoz, A. D. (2007). Metaheurísticas. Alianza Editorial.
Hernández, V. T. L. E. D. A. (2017, 17 agosto). Solución al problema P vs NP?
Meta-learning Lab.
https://mlearninglab.com/2017/08/17/solucion-al-problema-p-vs-np/