ผลต่างระหว่างรุ่นของ "ทฤษฎีความซับซ้อนในการคำนวณ"

เราเรียกปัญหาที่สามารถ[[ตัดสินได้|หาคำตอบได้]] ในเชิงทฤษฎี แต่ไม่สามารถนำมาใช้ได้จริง ว่าเป็นปัญหาที่ยาก (intractable) โดยมากแล้วเราจะแทนความง่ายของปัญหาด้วยการที่มีอัลกอริทึมที่ทำงานใช้เวลาเป็นฟังก์ชันพหุนามกับขนาดของอินพุต ปัญหา[[เอ็นพีบริบูรณ์]] ถูกเชื่อว่าเป็นปัญหาที่ยาก (ที่ใช้คำว่า "เชื่อ" ก็เพราะว่าการที่ปัญหาเอ็นพีบริบูรณ์จะยากหรือไม่นั้นขึ้นกับว่าพีเท่ากับเอ็นพีหรือไม่ หากว่าพีเท่ากับเอ็นพี เอ็นพีบริบูรณ์ทั้งหมดก็เป็นปัญหาที่ง่าย แต่หากไม่เท่ากัน เอ็นพีบริบูรณ์ก็เป็นตัวแทนของปัญหายากที่อยู่ภายในเอ็นพี) ส่วนปัญหาที่สามารถพีสูจน์ได้แน่นอนว่ายาก ก็คือปัญหา [[อีเอ็กซ์พีบริบูรณ์]] (EXP-complete) (เนื่องมาจาก [[ทฤษฎีลำดับชั้นของเวลา]])
 
 
== นักวิจัยที่มีชื่อเสียงที่เกี่ยวข้อง ==
* [[:en:Manindra Agrawal]]
* [[:en:Sanjeev Arora]]
* [[:en:Laszlo Babai]]
* [[:en:Manuel Blum]]
* [[สตีเฟน คุก]] (Stephen Cook)
* [[:en:Lance Fortnow]]
* [[:en:Juris Hartmanis]]
* [[:en:Russell Impagliazzo]]
* [[:en:Marek Karpinski]]
* [[ริชาร์ด คาร์ป]] (Richard Karp)
* [[เลโอนิด เลวิน]] (Leonid Levin)
* [[:en:Richard Lipton]]
* [[:en:Noam Nisan]]
* [[:en:Christos H. Papadimitriou]]
* [[:en:Alexander Razborov]]
* [[:en:Walter Savitch]]
* [[:en:Michael Sipser]]
* [[:en:Richard Stearns]]
* [[:en:Madhu Sudan]]
* [[:en:Leslie Valiant]]
* [[:en:Umesh Vazirani]]
* [[:en:Avi Wigderson]]
* [[:en:Andrew Yao]]
* [[:en:Eugene Yarovoi]]
 
[[หมวดหมู่:ทฤษฎีการคำนวณ]]
44,451

การแก้ไข