Czy Stephen Cook dostrzegł znaczenie wykazania, że SAT jest NP-twardy przed faktycznym udowodnieniem?

Jeśli dobrze rozumiem, aby udowodnić, że problem jest trudny NP, musisz wybrać wszystkie możliwe problemy które są w NP, a następnie udowodnić, że redukują się do za pomocą funkcji obliczania czasu wielomianowego, która odwzorowuje wystąpienia każdego z nich do przypadków . $A$ $B_{i}$ $A$ $B_{i}$ $A$

Po znalezieniu pierwszego trudnego problemu NP, stosując redukcje, możesz stwierdzić, że wiele innych problemów to NP Complete lub NP Hard. Wyobrażam sobie jednak, że to zależy. Jeśli masz pecha, być może wszystkie problemy zmniejszają się do , ale nie zmniejsza nigdzie indziej, więc twój dowód jest w zasadzie bezużyteczny. $B_{i}$ $A$ $A$

Moje pytanie dotyczy motywacji, za którą stoi Stephen Cook, pokazując, że problem SAT jest trudny NP. Czy widział duży potencjał tego problemu? Czy wiedział, że jeśli wykazałby, że ten problem jest NP trudny, to wiele innych problemów może być również trudnych do NP?

Krótko mówiąc, jaka jest historia tego dowodu? Ponieważ po przestudiowaniu jakiejś podstawowej teorii złożoności wydaje się, że ten dowód był jednym z najważniejszych w tej dziedzinie.

soft-question ho.history-overview cook-levin

— jsguy
źródło

Jeśli jest -kompletny, to z definicji jest w oprócz tego, że -hard. Więc dla każdego inna -Complete problemów musi być redukcja . Proponuję oddzielić ten fakt w pierwszych dwóch akapitach od pozostałych pytań, ponieważ jest to trywialne. Odpowiem na drugą część osobno.

A

$A$

N P

$\mathbb{NP}$

N P

$\mathbb{NP}$

N P

$\mathbb{NP}$

N P

$\mathbb{NP}$

C

$C$

A \leq C

$A \leq C$

— chazisop

Po pierwsze, nie sądzę, że jest to temat na tej stronie, wydaje się bardziej odpowiedni dla informatyki . Wydaje się, że nawet nie czytałeś gazety.

— Kaveh

Nawet jeśli nie byłoby innego problemu, nadal byłoby bardzo znaczące, że istnieje problem w NP, który jest uniwersalny dla NP. W artykule Steve udowadnia, że kilka innych problemów jest NP-zupełnych. AFAIU, znaczenie wyników było jasne dla uczestników konferencji.

— Kaveh

pytanie jest nieco zacofane. nikt nie mógł przewidzieć powszechnego znaczenia rozróżnienia P / NP w CS we wczesnych dniach (jego pełne implikacje wciąż są „odczuwalne”), najwyraźniej nikt nie wyobrażał sobie wtedy tego zjawiska (~ 1970). Cook był wtedy bliżej niż ktokolwiek inny. nawet przy zwykłej logice / kodzie / matematyce, czołowy wizjoner. ale wciąż był abstrakcyjny w pracy Cooksa. można porównać do „nierozstrzygalności” w pracy Turingsa z 1936 r. nierozstrzygalność była bardziej teoretyczna i nie wyobrażano jej, aby była tak znacząca i miała tak poważne implikacje w tym czasie.

— vzn

z drugiej strony jest kilka

— powodów, dla

Po pierwsze, Cook faktycznie pokazał, że problemem tego, czy wyrażenie logiczne jest tautologią, jest -kompletny w ramach redukcji Cooka . Dowód działa jednak, zastępując je redukcjami Karp, aby pokazać, że jest , w nowoczesnym tego słowa znaczeniu. $\mathbb{NP}$ $SAT$ $\mathbb{NP}$

Jeśli chodzi o to, czy Cook zrozumiał znaczenie -kompletnego problemu, którego nie ma w , przeglądanie faktycznej pracy pokazuje, że to zrobił. Uważam jednak, że dopiero po sporządzeniu przez Karpa listy 21 kompletnych problemów praktyczne znaczenie wyniku Cooka zaczęło być rozumiane. $\mathbb{NP}$ $\mathbb{P}$

— chazisop
źródło

Czy Stephen Cook dostrzegł znaczenie wykazania, że ​​SAT jest NP-twardy przed faktycznym udowodnieniem?

Czy Stephen Cook dostrzegł znaczenie wykazania, że SAT jest NP-twardy przed faktycznym udowodnieniem?