Stephen Cook viu o significado de mostrar que o SAT é NP-Hard antes de realmente provar?

Se eu entendi corretamente, para provar que o problema é NP difícil, você precisa escolher todos os possíveis problemas que estão no NP e depois provar que eles se reduzem a usando uma função computável de tempo polinomial, que mapeia instâncias de cada a instâncias de .$A$$B_{i}$$A$$B_{i}$$A$

Depois de encontrar o primeiro problema difícil do NP, usando reduções, você poderá descobrir que muitos outros problemas são NP Completo ou NP Difícil. No entanto, imagino que isso depende. Se você não tiver sorte, talvez todos os problemas com reduzidos para , mas não se reduza a nenhum outro lugar, então sua prova é essencialmente inútil.$B_{i}$$A$$A$

Minha pergunta é sobre a motivação de Stephen Cook, mostrando que o problema do SAT é difícil para o NP. Ele viu muito potencial por trás desse problema? Ele sabia que, se mostrasse que esse problema é NP difícil, muitos outros problemas também poderiam ser NP?

Em suma, qual é a história por trás dessa prova? Porque, depois de estudar alguma teoria básica da complexidade, realmente parece que essa prova foi uma das mais significativas nessa área.

Antes de tudo, Cook realmente mostrou que o problema de uma expressão lógica ser uma tautologia é completo nas reduções de Cook . A prova, no entanto, funciona substituindo-os por reduções de Karp para mostrar que S A T é N- P completo, no sentido moderno do termo.$\mathbb{NP}$$SAT$$\mathbb{NP}$

Quanto a saber se Cozinhe entendeu o significado de uma problema -completo não estar em P , passando o actual papel mostra que ele fez. No entanto, acredito que não foi até a lista de 21 problemas completos de Karp que o significado prático do resultado de Cook começou a ser entendido.$\mathbb{NP}$$\mathbb{P}$