Стивен Кук видел значение показа того, что SAT является NP-Hard, прежде чем на самом деле это доказать?

Если я правильно понимаю, чтобы доказать, что проблема является NP трудной, вам нужно выбрать все возможные проблемы которые есть в NP, а затем доказать, что они сводятся к , используя вычислимую функцию за полиномиальное время, которая отображает экземпляры каждого к экземплярам .$A$$B_{i}$$A$$B_{i}$$A$

Как только вы найдете первую сложную проблему NP, используя сокращения, вы можете обнаружить, что многие другие проблемы являются либо NP Complete, либо NP Hard. Однако я представляю, что это зависит. Если вам не повезло, то, возможно, все проблемы сводятся к , но нигде не уменьшает, поэтому ваши доказательства по существу бесполезны.$B_{i}$$A$$A$

Мой вопрос касается мотивации, которую Стивен Кук показывает, что проблема SAT - трудная задача. Видел ли он большой потенциал за этой проблемой? Знал ли он, что если он покажет, что эта проблема - NP-сложная, то можно показать, что многие другие проблемы также являются NP-сложными?

Короче говоря, какова история этого доказательства? Потому что после изучения некоторой базовой теории сложности действительно кажется, что это доказательство было одним из самых значительных в этой области.

Прежде всего, Кук на самом деле показал, что проблема того, является ли логическое выражение тавтологией, $\mathbb{NP}$-полный под Кука сокращений . Однако доказательство работает, заменяя их сокращениями Карпа, чтобы показать, что$SAT$ является $\mathbb{NP}$-полный, в современном понимании этого термина.

Что касается того, понял ли Кук значение $\mathbb{NP}$проблема не в $\mathbb{P}$, просматривая фактические бумаги, показывает, что он сделал. Тем не менее, я полагаю, что только после того, как в списке 21 полной проблемы Карпа стало понятно практическое значение результата Кука.