ผลต่างระหว่างรุ่นของ "ทฤษฎีความซับซ้อนในการคำนวณ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล โรบอต เพิ่ม: fi:Aikavaativuusluokka |
|||
บรรทัด 38:
== ปัญหา P<nowiki>=</nowiki>NP ==
ปัญหาที่สำคัญที่สุดในด้านทฤษฎีการคำนวณก็คือปัญหาที่ว่ากลุ่มความซับซ้อนของปัญหาพี และ เอ็นพี เป็นเซตที่เท่ากันหรือไม่ ซึ่งทาง [[:en:Clay Mathematics Institute|Clay Mathematics Institute]] ได้ตั้งรางวัลไว้สำหรับผู้ที่แก้ปัญหานี้ได้เป็นมูลค่าสูงถึง หนึ่งล้านดอลลาร์ (ดูรายละเอียดของปัญหาได้ใน [[กลุ่มความซับซ้อน พี และ เอ็นพี]] และ [[เครื่องจักรออราเคิล]])
ปัญหาของพีและเอ็นพีนั้น ทำให้เกิดการสร้างแนวความคิดที่สำคัญมากในการวิจัยสาขานี้ขึ้นมา ซึ่งก็คือแนวความคิดเกี่ยวกับ "ความยาก (hardness)" และ "ความบริบูรณ์ (completeness)" เราจะเรียกเซตของปัญหา X ว่ายากสำหรับเซตของปัญหา Y เมื่อปัญหาทุกปัญหาใน Y สามารถลดรูปอย่างง่ายไปเป็นปัญหาบางปัญหาใน X ได้ (สำหรับรายละเอียดการลดรูป ขอละไว้ในที่นี้) สำหรับคำว่า "ง่าย" ในการลดรูปนั้นจะมีความหมายแตกต่างกันไปขึ้นอยู่กับบริบทที่สนใจ เซตที่เป็น "เซตยาก" ที่เราสนใจมากที่สุดนั้นก็คือเซต [[เอ็นพีแบบยาก]] (NP-hard) และคำว่า "ง่าย" ในการลดรูปที่มักจะเป็นที่สนใจก็คือการลดรูปที่ใช้เวลาเป็นฟังก์ชันพหุนามของขนาดของข้อมูลป้อนเข้า
| |||