DAA - Clase P y NP
En Ciencias de la Computación se resuelven muchos problemas donde el objetivo es maximizar o minimizar algunos valores, mientras que en otros problemas tratamos de buscar si hay solución o no. Por lo tanto, los problemas se pueden clasificar de la siguiente manera:
Problema de optimizacion
Los problemas de optimización son aquellos cuyo objetivo es maximizar o minimizar algunos valores. Por ejemplo,
Encontrar el número mínimo de colores necesarios para colorear un gráfico determinado.
Encontrar el camino más corto entre dos vértices en un gráfico.
Problema de decisión
Hay muchos problemas para los cuales la respuesta es un Sí o un No. Estos tipos de problemas se conocen como decision problems. Por ejemplo,
Si un gráfico determinado se puede colorear con solo 4 colores.
Encontrar el ciclo hamiltoniano en un gráfico no es un problema de decisión, mientras que verificar un gráfico es hamiltoniano o no es un problema de decisión.
¿Qué es idioma?
Cada problema de decisión puede tener solo dos respuestas, sí o no. Por lo tanto, un problema de decisión puede pertenecer a un idioma si proporciona una respuesta "sí" para una entrada específica. Un idioma es la totalidad de entradas para las que la respuesta es sí. La mayoría de los algoritmos discutidos en los capítulos anteriores sonpolynomial time algorithms.
Para tamaño de entrada n, si la complejidad temporal del peor de los casos de un algoritmo es O(nk), dónde k es una constante, el algoritmo es un algoritmo de tiempo polinomial.
Algoritmos como la multiplicación de la cadena de matrices, la ruta más corta de una sola fuente, la ruta más corta de todos los pares, el árbol de expansión mínimo, etc. Sin embargo, existen muchos problemas, como el vendedor ambulante, el color óptimo del gráfico, los ciclos hamiltonianos, encontrar la ruta más larga en un gráfico y satisfacer una fórmula booleana, para la que no se conocen algoritmos de tiempo polinomial. Estos problemas pertenecen a una clase interesante de problemas, denominadaNP-Complete problemas, cuyo estado se desconoce.
En este contexto, podemos categorizar los problemas de la siguiente manera:
Clase P
La clase P está formada por aquellos problemas que se pueden resolver en tiempo polinomial, es decir, estos problemas se pueden resolver en el tiempo. O(nk) en el peor de los casos, donde k es constante.
Estos problemas se llaman tractable, mientras que otros se llaman intractable or superpolynomial.
Formalmente, un algoritmo es un algoritmo de tiempo polinomial, si existe un polinomio p(n) tal que el algoritmo pueda resolver cualquier instancia de tamaño n en un tiempo O(p(n)).
Problema que requiere Ω(n50) tiempo para resolver son esencialmente intratables para grandes n. El algoritmo de tiempo polinomial más conocido se ejecuta en el tiempoO(nk) por un valor bastante bajo de k.
Las ventajas de considerar la clase de algoritmos de tiempo polinomial es que todos los deterministic single processor model of computation se pueden simular entre sí con un polinomio lento-d como máximo
Clase NP
La clase NP está formada por aquellos problemas que son verificables en tiempo polinomial. NP es la clase de problemas de decisión para los que es fácil verificar la exactitud de una respuesta afirmada, con la ayuda de un poco de información adicional. Por lo tanto, no estamos pidiendo una forma de encontrar una solución, sino solo para verificar que una supuesta solución realmente sea correcta.
Todos los problemas de esta clase se pueden resolver en tiempo exponencial mediante una búsqueda exhaustiva.
P versus NP
Cada problema de decisión que se puede resolver mediante un algoritmo de tiempo polinomial determinista también se puede resolver mediante un algoritmo no determinista de tiempo polinomial.
Todos los problemas en P se pueden resolver con algoritmos de tiempo polinomial, mientras que todos los problemas en NP - P son intratables.
No se sabe si P = NP. Sin embargo, en NP se conocen muchos problemas con la propiedad de que si pertenecen a P, entonces se puede demostrar que P = NP.
Si P ≠ NP, hay problemas en NP que no están ni en P ni en NP-Complete.
El problema pertenece a la clase Psi es fácil encontrar una solución al problema. El problema pertenece aNP, si es fácil comprobar una solución que puede haber sido muy tediosa de encontrar.