|
Las clases P y NP
Los problemas se resuelven por medio de algoritmos, algunos de los cuales pueden resultar más costosos que otros. En Teoría de la Complejidad, se trata de analizar el costo de un algoritmo. Típicamente el costo es el tiempo que tarda el algoritmo en resolver el problema. El algoritmo presentado en la sección 4 resuelve el problema de los conjuntos imposibles, pero de una manera muy ineficiente. Incluso, si el número de elementos del conjunto a analizar crece linealmente, entonces el tiempo de respuesta de ese algoritmo también crece, pero exponencialmente.
Existen muchas familias de problemas, pero dos clases muy populares
son: P y NP-completo ([2,5]). En la clase P están todos los
problemas que se pueden resolver por un algoritmo en tiempo polinomial, con
respecto a las entradas. Esto quiere decir que existe un polinomio Dado que no se ha encontrado una solución eficiente al problema de los conjuntos imposibles, es importante intentar caracterizar este problema, ya sea como P (encontrando un algoritmo que resuelva el problema en tiempo polinomial) o bien clasificándolo como NP-completo (mostrando que es equivalente a otro problema NP-completo). Los autores quieren heredarle este reto a los lectores.
Revista digital Matemática, Educación e Internet.
|
que acota el tiempo que tarda el algoritmo en resolver un problema de
tamaño 
. Por su parte, los problemas NP-completo son aquellos donde
no es posible encontrar un algoritmo que resuelva el problema en un
tiempo polinomial.