¿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á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.

¿Qué es un tiempo polinómico?

En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico .

¿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ál es la diferencia entre un programa y un polinomio?

Decimos que ese programa estaría en «P», que significa que el problema se resuelve en tiempo «polinomial». Pero si el tiempo aumentara exponencialmente o factorialmente, o algo por encima de lo que crecería un polinomio, no estaría en «P».