Para que cualquier problema Q sea NP-completo, tiene que satisfacer AMBAS las siguientes propiedades:
PROPIEDAD # 1
Existe un algoritmo no determinista que resuelve Q en tiempo polinómico .
Dicho de otra manera, existe un procedimiento de verificación que se ejecuta en tiempo polinómico, de si un certificado de entrada dado I (que afirma ser una solución del problema) , es en realidad una solución o no.
(Tan pronto como haya probado lo anterior, se garantiza que
[matemáticas] Q \ en NP [/ matemáticas] )
PROPIEDAD # 2
Cualquier otro problema Q ‘(que previamente se demostró que estaba en NP ) es reducible a Q en tiempo polinómico.
(Si solo ha probado lo anterior (pero falló en la primera condición), se garantiza que [math] Q \ in NP ~ hard [/ math])
- ¿Cómo se representa a los usuarios en código en el sitio web de Quora o en cualquier otro sitio de redes sociales?
- ¿Qué SDK y lenguaje de programación debo usar para codificar algoritmos de aprendizaje automático para predicciones en tiempo real?
- ¿Cuál será la complejidad temporal de la relación de recurrencia T (n-1) + T (n-2) + c?
- ¿Diferencia entre algoritmo de relleno de inundación y relleno de límite en gráficos de computadora?
- ¿Cuáles son las diferencias entre los algoritmos que realizan la búsqueda en un gráfico y los algoritmos que realizan la búsqueda en un árbol?
Dado que SAT es np-complete, si logra reducir SAT a 3SAT en tiempo polinómico, es decir, [matemática] SAT \ leq _ {p} 3 ~ SAT [/ matemática] (observe la dirección de conversión), tiene éxito Alcanzó su intención.
Como clase general, estos son los problemas completos de NP más populares y sus reducciones: 
