Sabemos que cuando nos enfrentamos a un problema concreto, podemos generar una serie de algoritmos que permitan resolverlo. Se habla entonces del orden de complejidad de un problema es en realidad el mejor algoritmo que se conozca para resolverlo. Así pues, la complejidad puede clasificarse de la siguiente manera:
- Problemas Clase P. Los algoritmos de complejidad polinómica se dice que son tratables en el sentido de que suelen ser abordables en la práctica. Los problemas para los que se conocen algoritmos con esta complejidad se dice que forman la clase P. Aquellos problemas para los que la mejor solución que se conoce es de complejidad superior a la polinómica, se dice que son problemas intratables. Seria muy interesante encontrar alguna solución polinómica (o mejor) que permitiera abordarlos.
- Problemas Clase NP. Algunos de estos problemas intratables pueden caracterizarse por el hecho de que puede aplicarse un algoritmo polinómico para comprobar si una posible solución es válida o no. Esta característica lleva a un método de resolución no determinista consistente en aplicar heurísticos para obtener soluciones hipotéticas que se van desestimando (o aceptando) a ritmo polinómico. Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinómicos).
- Problemas Clase NP-completos. Se conoce una amplia variedad de problemas de tipo NP, de los cuales destacan algunos de ellos de extrema complejidad. Gráficamente podemos decir que algunos problemas se hayan en la “frontera externa” de la clase NP. Son problemas NP, y son los peores problemas posibles de clase NP. Estos problemas se caracterizan por ser todos “iguales” en el sentido de que si se descubriera una solución P para alguno de ellos, esta solución sería fácilmente aplicable a todos ellos. No se sabe si existe solución a este tipo de problemas, pero hay muchas dudas de que exista. Sin embargo, nadie ha encontrado una prueba al respecto.
Y todo esto viene a cuento porque en el sitio Abstruse Goose, en donde sde hacen tiras cómicas con temas científicos, no necesariamente todos de cómputo, plantea el siguiente problema:
Referencias: