DAA - ทฤษฎีบทของคุก
Stephen Cook นำเสนอทฤษฎีบทสี่ประการในกระดาษของเขา“ ความซับซ้อนของขั้นตอนการพิสูจน์ทฤษฎีบท” ทฤษฎีบทเหล่านี้ระบุไว้ด้านล่าง เราเข้าใจว่ามีการใช้คำศัพท์ที่ไม่รู้จักจำนวนมากในบทนี้ แต่เราไม่มีขอบเขตที่จะพูดถึงรายละเอียดทุกอย่าง
ต่อไปนี้เป็นทฤษฎีบทสี่ประการของ Stephen Cook -
ทฤษฎีบท -1
ถ้าเป็นชุด S ของสตริงได้รับการยอมรับโดยเครื่องทัวริงที่ไม่ได้กำหนดบางตัวภายในเวลาพหุนามจากนั้น S P-reducible เป็น {DNF tautologies}
ทฤษฎีบท -2
ชุดต่อไปนี้เป็น P-reducible ซึ่งกันและกันเป็นคู่ (และด้วยเหตุนี้แต่ละชุดจึงมีระดับความยากของพหุนามเท่ากัน): {tautologies}, {DNF tautologies}, D3, {sub-graph pair}
ทฤษฎีบท -3
สำหรับใด ๆ TQ(k) ประเภท Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ ไม่ถูกผูกไว้
มี TQ(k) ประเภท Q เช่นนั้น $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
ทฤษฎีบท -4
หากชุด S ของสตริงได้รับการยอมรับโดยเครื่องที่ไม่ได้กำหนดภายในเวลา T(n) = 2n, และถ้า TQ(k) เป็นฟังก์ชันประเภทที่ซื่อสัตย์ (เช่นแบบเรียลไทม์นับได้) Qแล้วมีค่าคงที่ Kดังนั้น S สามารถรับรู้ได้ด้วยเครื่องจักรที่กำหนดภายในเวลา TQ(K8n).
ประการแรกเขาเน้นความสำคัญของความสามารถในการลดเวลาพหุนาม หมายความว่าถ้าเรามีการลดเวลาพหุนามจากปัญหาหนึ่งไปยังอีกปัญหาหนึ่งสิ่งนี้จะช่วยให้มั่นใจได้ว่าอัลกอริทึมเวลาพหุนามจากปัญหาที่สองสามารถแปลงเป็นอัลกอริทึมเวลาพหุนามที่สอดคล้องกันสำหรับปัญหาแรกได้
ประการที่สองเขามุ่งความสนใจไปที่ระดับ NP ของปัญหาการตัดสินใจที่สามารถแก้ไขได้ในเวลาพหุนามโดยคอมพิวเตอร์ที่ไม่ได้กำหนด ปัญหาที่ยากที่สุดส่วนใหญ่เป็นของคลาสนี้ NP
ประการที่สามเขาพิสูจน์ให้เห็นว่าปัญหาเฉพาะอย่างหนึ่งใน NP มีคุณสมบัติที่ทุกปัญหาอื่น ๆ ใน NP สามารถลดลงเป็นพหุนามได้ หากปัญหาความน่าพอใจสามารถแก้ไขได้ด้วยอัลกอริธึมเวลาพหุนามดังนั้นทุกปัญหาใน NP ก็สามารถแก้ไขได้ในเวลาพหุนาม หากปัญหาใด ๆ ใน NP นั้นว่ายากแล้วปัญหาความน่าพอใจจะต้องว่ายาก ดังนั้นปัญหาความน่าพอใจจึงเป็นปัญหาที่ยากที่สุดใน NP
ประการที่สี่ Cook แนะนำว่าปัญหาอื่น ๆ ใน NP อาจมีส่วนร่วมกับปัญหาความน่าพอใจคุณสมบัตินี้ในการเป็นสมาชิกที่ยากที่สุดของ NP