- 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
- no dirigido hamiltoniano circuito
- 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 la investigación operativa, y más generalmente deayuda con la decisión son a menudo Np-completos, es decir, no conocemos ningún algoritmo que permita encontrar una solución óptima en tiempo polinomial, pero sabemos cómo obtener una solución factible en tiempo polinomial (por 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 ', también hay uno para P.
ES 
FR 
EN