¿Cuáles son los ejemplos de un problema NP-completo?

Veamos un ejemplo clásico de un problema NP-Completo: el problema del viajante. Dicho problema nos dice que debemos obtener el camino más corto que pase una vez por cada una de las N ciudades y que vuelva al punto de orígen. Sabes la distancia entre todas las ciudades y puedes ir de cualquier ciudad a cualquier otra en cualquier orden.

¿Cuál es la diferencia entre un problema NP-completo y un problema polinómico?

Eso significa que si un solo problema NP-Completo tiene una solución polinómica entonces por definición todos la tienen. Y vicecersa: si se demuestra que tan solo un problema NP-Completo no tiene solución en tiempo polinómico, entonces ninguno la tiene. Veamos un ejemplo clásico de un problema NP-Completo: el problema del viajante.

¿Cuál es la diferencia entre NP-hard y NP-completo?

La diferencia entre NP-Hard y NP-Completo, es que un problema NP-Completo es en sí mismo un problema NP y un problema NP-Hard no tiene por qué. De hecho, el conjunto NP-Completo es la interesección entre los conjuntos NP-Hard y NP. Por supuesto si P=NP entonces, NP queda definido como un subconjunto de NP-Hard.

¿Cuáles son los problemas de los que existe prueba de pertenencia a NP-completo?

Para ello resulta útil conocer algunos de los problemas de los que existe prueba de pertenencia a NP-completo. Algunos de los más famosos son: Problema de satisfacibilidad booleana (SAT) Problema de la mochila (knapsack) Problema del ciclo hamiltoniano. Problema del vendedor viajero. Problema de la clique.

¿Cuáles son los problemas naturales de P?

P es conocido por contener muchos problemas naturales, incluyendo las versiones de decisión de programa lineal, cálculo del máximo común divisor, y encontrar una correspondencia máxima. Algunos problemas naturales son completos para P, incluyendo la conectividad (o la accesibilidad) en grafos no dirigidos.

¿Cuáles son los problemas que se pueden resolver en tiempo polinómico?

Entre los problemas que se pueden resolver en tiempo polinómico nos encontramos con diversas variedades como los logarítmicos (log (n)), los lineales (n), los cuadráticos (n2), los cúbicos (n3),… Volviendo al ejemplo principal llegamos a la conclusión que la función de elevar al cuadrado está contenida en la clase P.