- Satisfacción
- Hacer clic
- Establecer embalaje
- Cubierta de vértice
- Establecer cubierta
- Conjunto de arco de retroalimentación
- Conjunto de nodos de comentarios
- Circuito hamiltoniano dirigido
- Circuito hamiltoniano no dirigido
- Hacer clic
- Programación de números enteros 0-1
- 3-SAT
- Número cromático
- Haga clic en la portada
- Cobertura exacta
- Coincidencia 3D
- Árbol de Steiner
- Golpeando el set
- Mochila
- Secuencia de trabajos
- Dividir
- Max-corte
- Número cromático
Reducción de polinomios
Los problemas de investigación operativa, y más generalmente de apoyo a la decisión, son a menudo Np-completos, es decir, no conocemos ningún algoritmo que nos permita encontrar una solución óptima en tiempo polinómico, pero sabemos cómo obtener una solución que se puede lograr en tiempo polinomial (mediante reducción polinomial).
Complejidad polinomial
a algoritmo es de complejidad polinomial si existe un polinomio P tal que el número de instrucciones elementales realizadas durante su ejecución en una instancia de tamaño n es como máximo P(n). Un problema es de complejidad polinomial si existe un algoritmo de complejidad polinomial que lo resuelve. Es importante recalcar que la representación de las estructuras de datos utilizadas no influye en la complejidad.
Reducción de polinomios
Un problema de decisión P se reduce a un problema de decisión P' si existe un algoritmo polinomial R que transforma cualquier entrada u de P en una entrada u'=R(u) de P' tal que u∈Sí(P) ⇔ u'∈ Si p').
Esto sugiere la siguiente implicación: si hay un algoritmo polinomial para P', entonces también hay uno para P.
