¿Stephen Cook vio la importancia de demostrar que SAT es NP-Hard antes de demostrarlo?

9

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 .UNAsiyoUNAsiyoUNA

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.siyoUNAUNA

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.

jsguy
fuente
1
Si es N P -completo, entonces, por definición, está en N P además de ser N P- duro. Así, por cada otro N P problema -Complete C que debe haber una reducción de A C . Le sugiero que separe este hecho en los dos primeros párrafos del resto de las preguntas, ya que es trivial. Contestaré la segunda parte por separado. UNAnortePAGSnortePAGSnortePAGSnortePAGSCUNAC
chazisop
77
Primero, no creo que esto sea sobre el tema de este sitio, esto parece más adecuado para la informática . Parece que ni siquiera has leído el periódico.
Kaveh
44
Incluso si no hubiera otro problema, sería muy significativo que haya un problema en NP que sea universal para NP. Y en el documento, Steve demuestra que algunos otros problemas son NP completos. AFAIU, la importancia de los resultados fue clara para las personas en la conferencia.
Kaveh
La pregunta es algo al revés. nadie podría haber previsto la importancia generalizada de la distinción P / NP en CS en los primeros días (sus implicaciones aún "se sentían"), aparentemente nadie imaginaba el fenómeno en ese momento (~ 1970). Cook estaba más cerca que nadie en ese momento. incluso con mera lógica / código / matemática, un visionario superior. pero, todavía era abstracto en el papel de Cook. se podría establecer un paralelismo con la "indecidibilidad" en el documento de Turings 1936. la indecidibilidad era más teórica y no se imaginaba que fuera tan significativa y tuviera tan importantes implicaciones aplicadas en ese momento.
vzn
Por otro lado, se puede argumentar que Gödel anticipó parte de la distinción / importancia P / NP en una carta a von Neumann 1956
vzn

Respuestas:

17

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.nortePAGSSUNATnortePAGS

nortePAGSPAGS

chazisop
fuente