Hat Stephen Cook erkannt, wie wichtig es ist, zu zeigen, dass SAT NP-hart ist, bevor er es tatsächlich bewiesen hat?

Wenn ich richtig verstehe, müssen Sie, um zu beweisen, dass Problem NP-schwer ist, alle möglichen Probleme B i auswählen , die sich in NP befinden, und dann beweisen, dass sie sich auf A reduzieren, indem Sie eine polynomialzeitberechnbare Funktion verwenden, die Instanzen jedes B i abbildet In den Fällen von A .$A$$B_{i}$$A$$B_{i}$$A$

Sobald Sie das erste NP-Problem gefunden haben, können Sie mithilfe von Reduzierungen feststellen, dass viele andere Probleme entweder NP-vollständig oder NP-schwer sind. Ich stelle mir jedoch vor, dass dies davon abhängt. Wenn Sie Pech haben, reduzieren sich vielleicht alle -Probleme auf A , aber A reduziert sich nirgendwo anders, sodass Ihr Beweis im Wesentlichen nutzlos ist.$B_{i}$$A$$A$

Meine Frage bezieht sich auf die Motivation, die Stephen Cook hinter sich hat, um zu zeigen, dass das SAT-Problem NP-schwer ist. Hat er viel Potenzial hinter diesem Problem gesehen? Wusste er, dass, wenn er zeigte, dass dieses Problem NP-schwer ist, viele andere Probleme auch NP-schwer sein könnten?

Kurz gesagt, was ist die Geschichte hinter diesem Beweis? Denn nach dem Studium einer grundlegenden Komplexitätstheorie scheint dieser Beweis wirklich einer der bedeutendsten in diesem Bereich zu sein.

$\mathbb{NP}$$SAT$$\mathbb{NP}$

$\mathbb{NP}$$\mathbb{P}$