La relación exacta entre las clases de complejidad y las complejidades de algoritmos [duplicado

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cuál es la definición de P, NP, NP-Complete y NP-Hard? 7 respuestas

¿Todos los algoritmos son la complejidad del tiempo polinomial pertenecen a la clase P? ¿Y la clase P no tiene ningún algoritmo que no tenga complejidad polinomial?

¿Todos los algoritmos son complejidad no polinómica pertenecen a NP o NP-HARD o ambos?

Solo estoy tratando de entender la relación básica.

Answer 1

$ P $ se define como la clase de problemas (de decisión) que tienen un algoritmo que los resuelve en tiempo polinomial (en un TM, o un modelo polinomialmente equivalente). Por lo tanto, $ P $ contiene exactamente estos problemas, no más y nada menos.

En cuanto a $ NP $: la situación es más delicada. Un problema está en $ NP $ si tiene un algoritmo no determinista que se ejecuta en tiempo polinómico. Una definición equivalente y más fácil de usar es que, dada una solución al problema, puede verificar su corrección en el tiempo polinomio en el tamaño del problema. Por ejemplo, dado un gráfico y un camino que afirma ser un hamiltoniano, puede verificar en tiempo polinomial que de hecho es un camino hamiltoniano. Por lo tanto, el problema de decidir si un gráfico tiene una ruta hamiltoniana está en $ NP $.

Aclaración: $ np $ es una clase de problemas, no de algoritmos. Un algoritmo no pertenece a $ NP $.

Ahora, se sabe que algunos problemas no tienen un algoritmo de tiempo polinomial. Esto no significa que estén en $ NP $. De hecho, se sabe que algunos problemas no están en $ NP $. Por ejemplo, cualquier problema de $ nexp $-hard.

Con respecto a los problemas de $ np $-hard: ya que no sabemos si $ P = NP $ o no, no sabemos si cada problema fuera de $ P $ es $ NP $ -hard. Si $ np = p $, entonces cada problema es $ np $ -hard (excepto $ sigma^*$ y $ showyset $).

Esta respuesta (que es, con mucho, incompleta) cubre aproximadamente 3 semanas de material en un curso básico de complejidad. Quizás considere leer a fondo un libro de texto, como la "Teoría de la computación" de Sipser.

Answer 2

Todos los algoritmos que resuelven algún problema de decisión en tiempo polinomial muestran que sus problemas están en $ P $. Pero ciertamente hay algoritmos que no toman tiempo polinomial para problemas en $ P $. Puede ordenar generando todas las permutaciones de $ N! $ De la entrada y verificar cada una si está ordenada. Ese algoritmo toma un tiempo más que exponencial, pero el problema tiene una solución en tiempo polinomial.