Si entiendo correctamente, para demostrar que el problema es NP difícil, debe elegir todos los problemas posibles B i que están en NP y luego demostrar que se reducen a A mediante una función computable de tiempo polinomial, que mapea instancias de cada B i a los casos de a .
Una vez que encuentre el primer problema difícil de NP, al usar reducciones puede encontrar que muchos otros problemas son NP Completo o NP Difícil. Sin embargo, me imagino que esto depende. Si no tiene suerte, entonces quizás todos problemas de B i se reduzcan a A , pero A no se reduzca en ningún otro lugar, por lo que su prueba es esencialmente inútil.
Mi pregunta es sobre la motivación de Stephen Cook detrás de mostrar que el problema SAT es NP difícil. ¿Vio mucho potencial detrás de este problema? ¿Sabía que si mostraba que este problema es NP difícil, entonces también se podría demostrar que muchos otros problemas son NP difícil?
En resumen, ¿cuál es la historia detrás de esta prueba? Porque después de estudiar algo de teoría básica de la complejidad, realmente parece que esta prueba fue una de las más significativas en esta área.
Respuestas:
En primer lugar, Cook demostró que el problema de si una expresión lógica es una tautología es completo bajo las reducciones de Cook . Sin embargo, la prueba funciona al reemplazarlos con reducciones de Karp para mostrar que S A T es N P -completo, en el sentido moderno del término.N P SA T N P
fuente