ในทฤษฎีความซับซ้อนของการคำนวณทฤษฎีบทคุก-เลวินหรือที่รู้จักกันในชื่อทฤษฎีบทของคุกกล่าวว่าปัญหาความสามารถในการทำให้เป็นจริงของบูลีน นั้น เป็น ปัญหา NP-completeนั่นคือ ปัญหานี้อยู่ในกลุ่มNPและปัญหาใดๆ ในกลุ่ม NP สามารถลดรูปได้ในเวลาพหุนามโดยเครื่องจักรทัวริงแบบกำหนดได้ให้กลายเป็นปัญหาความสามารถในการทำให้เป็นจริงของบูลีน

ทฤษฎีบทนี้ตั้งชื่อตามStephen CookและLeonid Levinการพิสูจน์เป็นผลงานของRichard Karpโดยอิงจากการพิสูจน์ก่อนหน้านี้ (โดยใช้แนวคิดการลดรูปที่แตกต่างกัน) โดย Cook ^{[ 1 ]}

ผลลัพธ์ที่สำคัญอย่างหนึ่งจากทฤษฎีบทนี้คือ หากมีอัลกอริทึมแบบกำหนดเวลาเชิงพหุนามสำหรับการแก้ปัญหาความน่าพอใจของบูลีนแล้ว ปัญหา NP ทุก ปัญหาจะสามารถแก้ไขได้ด้วยอัลกอริทึมแบบกำหนดเวลาเชิงพหุนามเช่นกัน คำถามที่ว่ามีอัลกอริทึมดังกล่าวสำหรับการแก้ปัญหาความน่าพอใจของบูลีนอยู่หรือไม่ จึงเทียบเท่ากับปัญหา P เทียบกับ NPซึ่งยังคงได้รับการพิจารณาอย่างกว้างขวางว่าเป็นปัญหาที่สำคัญที่สุดที่ยังแก้ไม่ตกในวิทยาการคอมพิวเตอร์เชิงทฤษฎี

แนวคิดเรื่องNP-completenessได้รับการพัฒนาขึ้นในช่วงปลายทศวรรษ 1960 และต้นทศวรรษ 1970 โดยนักวิจัยในอเมริกาเหนือและสหภาพโซเวียตในปี 1971 Stephen Cookได้ตีพิมพ์บทความของเขาเรื่อง "ความซับซ้อนของขั้นตอนการพิสูจน์ทฤษฎีบท" ^{[ 2 ]}ในเอกสารการประชุมของ ACM Symposium on Theory of Computingที่ เพิ่งก่อตั้งขึ้นใหม่ บทความต่อมาของRichard Karp เรื่อง "ความสามารถในการลดรูปในหมู่ปัญหาเชิงการจัดเรียง" ^{[ 1 ]}ได้สร้างความสนใจใหม่ในบทความของ Cook โดยให้รายการปัญหา NP-complete จำนวน 21 ข้อ Karp ยังได้แนะนำแนวคิดเรื่องความสมบูรณ์ที่ใช้ในคำจำกัดความปัจจุบันของ NP-completeness (เช่น โดยการลดรูปหลายหนึ่งในเวลาพหุนาม ) Cook และ Karp ต่างได้รับรางวัล Turing Awardสำหรับงานนี้

ความสนใจเชิงทฤษฎีใน NP-completeness ยังได้รับการส่งเสริมจากผลงานของ Theodore P. Baker, John Gill และRobert Solovayซึ่งแสดงให้เห็นในปี 1975 ว่าการแก้ปัญหา NP ใน แบบจำลอง เครื่องออราเคิล บางแบบ ต้องใช้เวลาแบบเลขชี้กำลัง นั่นคือ มีออราเคิลA อยู่ ซึ่งสำหรับคลาสความซับซ้อนของเวลาแบบกำหนดที่ต่ำกว่าเลขชี้กำลัง T ทั้งหมด คลาสความซับซ้อนแบบสัมพัทธ์ NP ^{Aไม่ใช่}เซตย่อยของ T ^Aโดยเฉพาะ สำหรับออราเคิลนี้ P ^A  ≠ NP ^{A [ 3} ]

ในสหภาพโซเวียต ผลลัพธ์ที่เทียบเท่ากับของ Baker, Gill และ Solovay ได้รับการตีพิมพ์ในปี 1969 โดย M. Dekhtiar ^{[ 4 ]}ต่อมาบทความของLeonid Levin เรื่อง "ปัญหาการค้นหาสากล" ^{[ 5 ]}ได้รับการตีพิมพ์ในปี 1973 แม้ว่าจะมีการกล่าวถึงในการสนทนาและส่งเพื่อตีพิมพ์เมื่อไม่กี่ปีก่อนหน้านั้นก็ตาม

แนวทางของเลวินแตกต่างจากของคุกและคาร์ปเล็กน้อยตรงที่เขาพิจารณาปัญหาการค้นหาซึ่งต้องค้นหาคำตอบแทนที่จะเพียงแค่ตรวจสอบว่าคำตอบนั้นมีอยู่จริงหรือไม่ เขาได้เสนอโจทย์ปัญหาการค้นหาแบบ NP-complete หรือปัญหาแบบสากล จำนวน 6 ข้อ นอกจากนี้ เขายังพบอัลกอริทึมสำหรับแต่ละปัญหาเหล่านี้ที่สามารถแก้ปัญหาได้ในเวลาที่เหมาะสมที่สุด (โดยเฉพาะอย่างยิ่ง อัลกอริทึมเหล่านี้จะทำงานในเวลาพหุนามก็ต่อเมื่อP = NP เท่านั้น )

ปัญหาการตัดสินใจจัดอยู่ในกลุ่ม NPหากสามารถตัดสินใจได้ด้วยเครื่องจักรทัวริงแบบไม่กำหนด (nondeterministic Turing machine)ในเวลาพหุนาม (polynomial time )

ตัวอย่างหนึ่งของปัญหาความสามารถในการทำให้เป็นจริงของนิพจน์บูลีนคือนิพจน์บูลีนที่รวมตัวแปรบูลีนโดยใช้ตัวดำเนินการบูลีนนิพจน์ดังกล่าวจะสามารถหาคำตอบได้หากมีการกำหนดค่าความจริงให้กับตัวแปรเหล่านั้นแล้วทำให้นิพจน์ทั้งหมดเป็นจริง

กำหนดให้มีปัญหาการตัดสินใจใดๆ ในกลุ่มปัญหา NP ให้สร้างเครื่องจักรแบบไม่กำหนด (non-deterministic machine) ที่สามารถแก้ปัญหานั้นได้ในเวลาพหุนาม (polynomial time) จากนั้น สำหรับแต่ละอินพุตของเครื่องจักรนั้น ให้สร้างนิพจน์บูลีน (Boolean expression) ที่คำนวณว่าเมื่อป้อนอินพุตเฉพาะนั้นเข้าไปในเครื่องจักร เครื่องจักรจะทำงานได้อย่างถูกต้องหรือไม่ และเครื่องจักรจะหยุดทำงานและตอบว่า "ใช่" หรือไม่ นิพจน์นั้นจะเป็นจริงได้ก็ต่อเมื่อมีวิธีที่เครื่องจักรจะทำงานได้อย่างถูกต้องและตอบว่า "ใช่" ดังนั้น ความสามารถในการเป็นจริงของนิพจน์ที่สร้างขึ้นจึงเทียบเท่ากับการถามว่าเครื่องจักรจะตอบว่า "ใช่" หรือไม่

การพิสูจน์นี้อ้างอิงจากการพิสูจน์ของGarey & Johnsonในปี 1979 หน้า 38–44 ส่วนที่ 2.6

การพิสูจน์ว่าปัญหาความพึงพอใจของบูลีน (SAT) เป็นปัญหา NP-complete นั้นมีสองส่วน ส่วนแรกคือการแสดงว่า SAT เป็นปัญหา NP ส่วนที่สองคือการแสดงว่าทุกปัญหา NP สามารถลดรูปไปเป็นตัวอย่างของปัญหา SAT ได้โดยใช้การลดรูปหลายต่อหนึ่ง (many-one reduction ) ที่ใช้เวลาในการคำนวณแบบพหุนาม

SAT อยู่ในกลุ่ม NP เพราะการกำหนดค่าบูลีนให้กับตัวแปรบูลีนใดๆ ที่อ้างว่าสอดคล้องกับนิพจน์ที่กำหนด สามารถตรวจสอบได้ในเวลาพหุนามโดยเครื่องทัวริงแบบกำหนดได้ (ข้อความที่ตรวจสอบได้ในเวลาพหุนามโดยเครื่องทัวริงแบบกำหนดได้และแก้ได้ในเวลาพหุนามโดยเครื่องทัวริงแบบไม่กำหนดได้นั้นเทียบเท่ากัน และสามารถหาหลักฐานการพิสูจน์ได้ในตำราหลายเล่ม เช่น หนังสือIntroduction to the Theory of Computation ของ Sipser ส่วนที่ 7.3 รวมถึงบทความ Wikipedia เกี่ยวกับ NP ด้วย )

สมมติว่าปัญหาที่กำหนดใน NP สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบไม่กำหนด (nondeterministic Turing machine ) โดยที่คือเซตของสถานะคือตัวอักษรของสัญลักษณ์เทปคือสถานะเริ่มต้นคือเซตของสถานะที่ยอมรับได้ และคือความสัมพันธ์ของการเปลี่ยนสถานะ สมมติเพิ่มเติมว่ายอมรับหรือปฏิเสธตัวอย่างของปัญหาหลังจากขั้นตอนการคำนวณอย่างมากที่สุด โดยที่คือขนาดของตัวอย่าง และคือฟังก์ชันพหุนาม ${\displaystyle M=(Q,\Sigma ,s,F,\delta )}$${\displaystyle Q}$${\displaystyle \Sigma }$${\displaystyle s\in Q}$${\displaystyle F\subseteq Q}$${\displaystyle \delta \subseteq ((Q\setminus F)\times \Sigma )\times (Q\times \Sigma \times \{-1,+1\})}$${\displaystyle M}$${\displaystyle p(n)}$${\displaystyle n}$${\displaystyle p}$

สำหรับแต่ละอินพุตให้ระบุค่าบูลีนที่สามารถเป็นจริงได้ก็ต่อเมื่อเครื่องยอมรับค่าเท่านั้น ${\displaystyle I}$${\displaystyle B}$${\displaystyle M}$${\displaystyle I}$

นิพจน์บูลีนใช้ตัวแปรที่กำหนดไว้ในตารางต่อไปนี้ โดยที่คือสถานะของเครื่องคือตำแหน่งของเทปคือสัญลักษณ์ของเทป และคือหมายเลขของขั้นตอนการคำนวณ ${\displaystyle q\in Q}$${\displaystyle -p(n)\leq i\leq p(n)}$${\displaystyle j\in \Sigma }$${\displaystyle 0\leq k\leq p(n)}$

ตัวแปร	การตีความที่ตั้งใจไว้	กี่? [ 6 ]
${\displaystyle T_{i,j,k}}$	เป็นจริงหากเซลล์เทปมีสัญลักษณ์ในขั้นตอนการคำนวณ ${\displaystyle i}$${\displaystyle j}$${\displaystyle k}$	${\displaystyle O(p(n)^{2})}$
${\displaystyle H_{i,k}}$	เป็นจริงหากหัวอ่าน/เขียนของ 's อยู่ที่เซลล์เทปในขั้นตอนการคำนวณ ${\displaystyle M}$${\displaystyle i}$${\displaystyle k}$	${\displaystyle O(p(n)^{2})}$
${\displaystyle Q_{q,k}}$	เป็นจริงหากอยู่ในสถานะณ ขั้นตอนการคำนวณ ${\displaystyle M}$${\displaystyle q}$${\displaystyle k}$	${\displaystyle O(p(n))}$

กำหนดให้การแสดงออกเชิงบูลีนเป็นการเชื่อมต่อของการแสดงออกย่อยในตารางต่อไปนี้ สำหรับทุกค่าของและ: ${\displaystyle B}$${\displaystyle -p(n)\leq i\leq p(n)}$${\displaystyle 0\leq k\leq p(n)}$

การแสดงออก	เงื่อนไข	การตีความ	เท่าไหร่?
${\displaystyle T_{i,j,0}}$	เซลล์เทปเริ่มต้นมีสัญลักษณ์${\displaystyle i}$${\displaystyle j}$	เนื้อหาเริ่มต้นของเทป สำหรับและนอกเหนือจากข้อมูลป้อนเข้าจริงสัญลักษณ์เริ่มต้นคือสัญลักษณ์ค่าเริ่มต้น/ว่างเปล่าพิเศษ ${\displaystyle i>n-1}$${\displaystyle i<0}$${\displaystyle I}$	${\displaystyle O(p(n))}$
${\displaystyle Q_{s,0}}$		สถานะเริ่มต้นของ. ${\displaystyle M}$	1
${\displaystyle H_{0,0}}$		ตำแหน่งเริ่มต้นของหัวอ่าน/เขียน	1
${\displaystyle \neg T_{i,j,k}\lor \neg T_{i,j',k}}$	${\displaystyle j\neq j'}$	แต่ละช่องเทปสามารถแสดงสัญลักษณ์ได้ไม่เกินหนึ่งสัญลักษณ์	${\displaystyle O(p(n)^{2})}$
${\displaystyle \bigvee _{j\in \Sigma }T_{i,j,k}}$		อย่างน้อยหนึ่งสัญลักษณ์ต่อเซลล์เทป	${\displaystyle O(p(n)^{2})}$
${\displaystyle T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}}$	${\displaystyle j\neq j'}$	เทปจะไม่มีการเปลี่ยนแปลงใดๆ เว้นแต่จะมีการเขียนทับโดยหัวหน้างาน	${\displaystyle O(p(n)^{2})}$
${\displaystyle \lnot Q_{q,k}\lor \lnot Q_{q',k}}$	${\displaystyle q\neq q'}$	ครั้งละไม่เกินหนึ่งรัฐ	${\displaystyle O(p(n))}$
${\displaystyle \bigvee _{q\in Q}Q_{q,k}}$		อย่างน้อยครั้งละหนึ่งรัฐ	${\displaystyle O(p(n))}$
${\displaystyle \lnot H_{i,k}\lor \lnot H_{i',k}}$	${\displaystyle i\neq i'}$	สามารถจัดท่าศีรษะได้ครั้งละหนึ่งท่าเท่านั้น	${\displaystyle O(p(n)^{3})}$
${\displaystyle \bigvee _{-p(n)\leq i\leq p(n)}H_{i,k}}$		ควรจัดท่าศีรษะอย่างน้อยหนึ่งท่าในแต่ละครั้ง	${\displaystyle O(p(n)^{2})}$
${\displaystyle {\begin{array}{l}(H_{i,k}\land Q_{q,k}\land T_{i,\sigma ,k})\to \\\bigvee _{((q,\sigma ),(q',\sigma ',d))\in \delta }(H_{i+d,\ k+1}\land Q_{q',\ k+1}\land T_{i,\ \sigma ',\ k+1})\end{array}}}$	${\displaystyle k<p(n)}$	การเปลี่ยนสถานะที่เป็นไปได้ในขั้นตอนการคำนวณเมื่อหัวอยู่ที่ตำแหน่ง. ${\displaystyle k}$${\displaystyle i}$	${\displaystyle O(p(n)^{2})}$
${\displaystyle \bigvee _{0\leq k\leq p(n)}\bigvee _{f\in F}Q_{f,k}}$		ต้องเสร็จสิ้นในสถานะที่ยอมรับได้ ไม่เกินขั้นตอนที่. ${\displaystyle p(n)}$	1

หากมีการคำนวณที่ยอมรับได้สำหรับอินพุตแล้วก็สามารถทำให้เป็นจริงได้โดยการกำหนดค่าและการตีความที่ตั้งใจไว้ ในทางกลับกัน หากสามารถทำให้เป็นจริงได้ ก็จะมีการคำนวณที่ยอมรับได้สำหรับอินพุตที่ทำตามขั้นตอนที่ระบุโดยการกำหนดค่าให้กับตัวแปร ${\displaystyle M}$${\displaystyle I}$${\displaystyle B}$${\displaystyle T_{i,j,k}}$${\displaystyle H_{i,k}}$${\displaystyle Q_{i,k}}$${\displaystyle B}$${\displaystyle M}$${\displaystyle I}$

มีตัวแปรบูลีน แต่ละตัวสามารถเข้ารหัสได้ในพื้นที่จำนวนข้อความคือ^{[ 7 ]}ดังนั้นขนาดของจึงเป็นดังนั้นการแปลงจึงเป็นการลดจำนวนหนึ่งหลายรายการในเวลาพหุนามอย่างแน่นอน ตามที่ต้องการ ${\displaystyle O(p(n)^{2})}$${\displaystyle O(\log p(n))}$${\displaystyle O(p(n)^{3})}$${\displaystyle B}$${\displaystyle O(\log(p(n))p(n)^{3})}$

เฉพาะแถวแรกของตาราง ( ) เท่านั้นที่ขึ้นอยู่กับสตริงอินพุตบรรทัดที่เหลือขึ้นอยู่กับความยาวของอินพุตและเครื่องจักร เท่านั้น โดยจะกำหนดรูปแบบการคำนวณทั่วไปของ สำหรับ ขั้นตอน สูงสุด${\displaystyle T_{i,j,0}}$${\displaystyle I}$${\displaystyle n}$${\displaystyle M}$${\displaystyle M}$${\displaystyle p(n)}$

การแปลงนี้ใช้พหุนามอย่างกว้างขวางดังนั้น การพิสูจน์ข้างต้นจึงไม่ใช่การพิสูจน์เชิงสร้างสรรค์ : แม้ว่าจะทราบค่า แล้วก็ตามเมื่อพิจารณาว่าปัญหาที่กำหนดอยู่ในกลุ่ม NP การแปลงก็ไม่สามารถคำนวณได้อย่างมีประสิทธิภาพ เว้นแต่จะทราบขอบเขตบนของความซับซ้อนเชิงเวลาของ ด้วย ${\displaystyle p(n)}$${\displaystyle M}$${\displaystyle p(n)}$${\displaystyle M}$

ในขณะที่วิธีการข้างต้นเข้ารหัสเครื่องจักรทัวริงที่ไม่กำหนดในความซับซ้อน วรรณกรรมอธิบายวิธีการที่ซับซ้อนกว่าในความซับซ้อน[ ^{8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] ผลลัพธ์}กึ่งเชิงเส้นปรากฏขึ้นครั้งแรกเจ็ดปีหลังจากที่ Cook ตีพิมพ์ผลงานต้นฉบับ ${\displaystyle O(\log(p(n))p(n)^{3})}$${\displaystyle O(p(n)\log(p(n)))}$

การใช้ SAT เพื่อพิสูจน์การมีอยู่ของปัญหา NP-complete สามารถขยายไปสู่ปัญหาการคำนวณอื่นๆ ในตรรกะ และไปสู่ความสมบูรณ์สำหรับคลาสความซับซ้อน อื่นๆ ได้ ปัญหา สูตรบูลีนแบบมีตัวบ่งปริมาณ (QBF) เกี่ยวข้องกับสูตรบูลีนที่ขยายเพื่อรวมตัวบ่งปริมาณสากล แบบซ้อนกัน และตัวบ่งปริมาณเชิงมีอยู่สำหรับตัวแปร ปัญหา QBF สามารถใช้เพื่อเข้ารหัสการคำนวณด้วยเครื่องทัวริงที่จำกัดความซับซ้อนของพื้นที่พหุนามซึ่งพิสูจน์ได้ว่ามีปัญหา (การรับรู้สูตรบูลีนแบบมีตัวบ่งปริมาณที่เป็นจริง) ที่เป็นPSPACE-completeในทำนองเดียวกัน สูตรบูลีนแบบมีตัวบ่งปริมาณการพึ่งพาจะเข้ารหัสการคำนวณด้วยเครื่องทัวริงที่จำกัดความซับซ้อนของพื้นที่ลอการิทึมซึ่งพิสูจน์ได้ว่ามีปัญหาที่เป็นNL- complete ^{[ 13 ] [ 14 ]}

บทพิสูจน์แสดงให้เห็นว่าทุกปัญหาใน NP สามารถลดรูปได้ในเวลาพหุนาม (อันที่จริงพื้นที่ลอการิทึมก็เพียงพอแล้ว) ไปเป็นอินสแตนซ์ของปัญหาความสามารถในการทำให้เป็นจริงของบูลีน ซึ่งหมายความว่าหากปัญหาความสามารถในการทำให้เป็นจริงของบูลีนสามารถแก้ไขได้ในเวลาพหุนามโดยเครื่องจักรทัวริงแบบกำหนดได้ปัญหาทั้งหมดใน NP ก็จะสามารถแก้ไขได้ในเวลาพหุนามเช่นกัน ดังนั้นระดับความซับซ้อน NP จะเท่ากับระดับความซับซ้อน P

ความสำคัญของ NP-completeness ได้รับการชี้แจงอย่างชัดเจนจากการตีพิมพ์ บทความสำคัญของ Richard Karp ในปี 1972 เรื่อง "Reducibility among combinatorial problems" ซึ่งเขาแสดงให้เห็นว่าปัญหาเชิงการจัดเรียงและทฤษฎีกราฟที่หลากหลาย 21 ปัญหาซึ่งแต่ละปัญหามีชื่อเสียงในด้านความยากในการแก้ไขนั้น ล้วนเป็น NP-complete ^{[ 1 ]}

คาร์ปแสดงให้เห็นว่าปัญหาแต่ละข้อของเขาเป็น NP-complete โดยการลดปัญหาอื่น (ซึ่งแสดงให้เห็นแล้วว่าเป็น NP-complete) ให้เป็นปัญหานั้น ตัวอย่างเช่น เขาแสดงให้เห็นว่าปัญหา 3SAT ( ปัญหาความพึงพอใจของบูลีนสำหรับนิพจน์ในรูปแบบปกติเชิงเชื่อมโยง (CNF) ที่มีตัวแปรหรือการปฏิเสธของตัวแปรสามตัวต่อประโยค) เป็น NP-complete โดยแสดงวิธีการลด (ในเวลาพหุนาม) อินสแตนซ์ใด ๆ ของ SAT ให้เป็นอินสแตนซ์ที่เทียบเท่าของ 3SAT ^{[ 15 ]}

Garey และ Johnson นำเสนอปัญหา NP-complete มากกว่า 300 ปัญหาในหนังสือComputers and Intractability: A Guide to the Theory of NP-Completeness [ ^{16 ]}และยังคงมีการค้นพบปัญหาใหม่ๆ ที่อยู่ในคลาสความซับซ้อนดัง ^{กล่าว}

แม้ว่าปัญหา SAT ในทางปฏิบัติหลายๆ กรณีจะสามารถแก้ไขได้ด้วยวิธีการฮิวริสติกแต่คำถามที่ว่ามีอัลกอริทึมแบบกำหนดเวลาเชิงพหุนามสำหรับ SAT (และด้วยเหตุนี้จึงรวมถึงปัญหา NP-complete อื่นๆ ทั้งหมด) หรือไม่นั้น ยังคงเป็นปัญหาที่ยังแก้ไม่ตกที่มีชื่อเสียง แม้ว่าจะมีการพยายามอย่างหนักมานานหลายทศวรรษโดยนักทฤษฎีความซับซ้อนนักตรรกศาสตร์ทางคณิตศาสตร์และอื่นๆ สำหรับรายละเอียดเพิ่มเติม โปรดดูบทความปัญหา P เทียบกับ NP