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

โรบอต แก้ไข: fr:Théorie de la complexité des algorithmes; ประทิ่นเปลี่ยนแปลง
(โรบอต เพิ่ม: tr:Hesap karmaşıklığı kuramı)
(โรบอต แก้ไข: fr:Théorie de la complexité des algorithmes; ประทิ่นเปลี่ยนแปลง)
'''ทฤษฎีความซับซ้อนในการคำนวณ''' (Computational Complexity Theory) เป็นสาขาหนึ่งของ [[ทฤษฎีการคำนวณ]] ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า). ในบางกรณีเราอาจจะสนใจการวิเคราะห์ปริมาณอื่น ๆ ที่นอกเหนือไปจากพื้นที่กับเวลา ยกตัวอย่างเช่น ใน[[การประมวลผลแบบขนาน]] เราอาจจะวิเคราะห์ว่าต้องใช้[[หน่วยประมวลผล]]กี่ตัวในการแก้ปัญหาที่กำหนด. ทฤษฎีความซับซ้อนต่างจาก [[ทฤษฎีการคำนวณได้]] ที่จะเน้นไปในการวิเคราะห์ว่าปัญหาสามารถแก้ได้หรือไม่ โดยไม่สนใจทรัพยากรที่ใช้ในการแก้ปัญหา
 
== ภาพรวม ==
ภายหลังจากที่สามารถระบุได้ว่า ปัญหาใดสามารถแก้ได้ และปัญหาใดที่แก้ไม่ได้ เรามักจะเกิดคำถามขึ้นอีกว่าในบรรดาปัญหาที่แก้ได้ ซึ่งเป็นกลุ่มของ[[ฟังก์ชันที่คำนวณได้]]นั้น มีความซับซ้อนอยู่ในระดับใด จุดนี้เป็นความสนใจหลักของ [[ทฤษฎีความซับซ้อนในการคำนวณ]]
 
'''ตัวอย่าง:''' การตัดหญ้าในสวนใช้เวลาในการทำงานเป็นเชิงเส้น เพราะว่าถ้าสนามหญ้าใหญ่กว่าเดิมเท่าตัว เราก็ต้องใช้เวลาในการตัดหญ้ามากขึ้นเป็นเท่าตัว แต่สำหรับการเปิดหาคำศัพท์ในพจนานุกรมนั้น เวลาที่ใช้ในการทำงานจะเป็น[[ลอการิทึม]]ของขนาดข้อมูลป้อนเข้า เพราะว่าสำหรับพจนานุกรมที่มีขนาดเพิ่มเป็นเท่าตัว เราทำงานเพิ่มขึ้นเพียงหนึ่งขั้นตอน (เปิดพจนานุกรมไปตรงกลางแล้วตรวจสอบว่าคำศัพท์ที่เรากำลังมองหาอยู่ในฝั่งใดของพจนานุกรม ซึ่งวิธีนี้จะลดขนาดของปัญหาลงครึ่งหนึ่งทุกครั้งที่มีการเปิดพจนานุกรม)
 
== ปัญหาการตัดสินใจ ==
 
ส่วนใหญ่แล้ว ทฤษฎีเกี่ยวกับความซับซ้อนในการคำนวณ จะสนใจกลุ่มของ[[ปัญหาการตัดสินใจ]]. ซึ่งปัญหาที่อยู่ในกลุ่มนี้ จะมีคำตอบเพียงสองแบบก็คือ "ใช่" และ "ไม่ใช่" ยกตัวอย่างเช่นปัญหาที่ถามว่าจำนวนหนึ่ง ๆ เป็นจำนวนเฉพาะหรือไม่. ปัญหาในกลุ่มนี้อาจมองได้อีกแบบหนึ่งก็คือ มองเป็น [[ภาษา (ทฤษฎีออโตมาตา)|ภาษา]] ซึ่งเป็นเซตของสตริงความยาวจำกัด. สำหรับปัญหาการตัดสินใจปัญหาหนึ่ง เราอาจจะมองว่า มันคือภาษาที่มีสมาชิกในเซตเป็นตัวอย่างปัญหาทั้งหมดที่ให้คำตอบเป็น "ใช่".
ทฤษฎีบทที่สำคัญอันหนึ่งในด้านทฤษฎีความซับซ้อนในการคำนวณก็คือ ไม่ว่าปัญหาของเราจะยากขนาดไหน เราจะมีปัญหาที่ยากกว่าเสมอ หากเราพิจารณาเฉพาะปัญหาที่สามารถแก้ได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของข้อมูลป้อนเข้า เราสามารถอธิบายในจุดนี้ได้ด้วย[[ทฤษฎีลำดับชั้นของเวลา]] ([[:en:time hierarchy theorem|time hierarchy theorem]])ที่กล่าวไว้ว่า หากเราให้คอมพิวเตอร์ของเราทำงานด้วยเวลาที่มากขึ้น ปัญหาที่เราสามารถแก้ได้ก็จะเพิ่มขึ้น (นั่นก็คือ มีปัญหาที่แก้ไม่ได้ถ้าไม่มีการเพิ่มเวลา) [[ทฤษฎีลำดับชั้นของเนื้อที่]] (space hierarchy theorem) ก็จะกล่าวในเชิงคล้ายกัน เพียงแต่มุ่งความสนใจในเรื่องของเนื้อที่ที่อนุญาตให้มีการใช้งานได้
 
== กลุ่มของความซับซ้อนของปัญหา ==
 
ปัญหาการตัดสินใจสามารถแบ่งออกได้เป็นหลายๆกลุ่ม โดยที่แต่ละกลุ่มจะประกอบไปด้วยปัญหาที่มีความยากเท่าเทียมกัน
เช่นเดียวกันกับเรื่องของความยาก เซตบริบูรณ์ที่สำคัญที่สุดก็คือ เซต[[เอ็นพีบริบูรณ์]]
 
== ความยาก (Intractability) ==
 
เราเรียกปัญหาที่สามารถ[[ตัดสินได้|หาคำตอบได้]] ในเชิงทฤษฎี แต่ไม่สามารถนำมาใช้ได้จริง ว่าเป็นปัญหาที่ยาก (intractable) โดยมากแล้วเราจะแทนความง่ายของปัญหาด้วยการที่มีอัลกอริทึมที่ทำงานใช้เวลาเป็นฟังก์ชันพหุนามกับขนาดของอินพุต ปัญหา[[เอ็นพีบริบูรณ์]] ถูกเชื่อว่าเป็นปัญหาที่ยาก (ที่ใช้คำว่า "เชื่อ" ก็เพราะว่าการที่ปัญหาเอ็นพีบริบูรณ์จะยากหรือไม่นั้นขึ้นกับว่าพีเท่ากับเอ็นพีหรือไม่ หากว่าพีเท่ากับเอ็นพี เอ็นพีบริบูรณ์ทั้งหมดก็เป็นปัญหาที่ง่าย แต่หากไม่เท่ากัน เอ็นพีบริบูรณ์ก็เป็นตัวแทนของปัญหายากที่อยู่ภายในเอ็นพี) ส่วนปัญหาที่สามารถพีสูจน์ได้แน่นอนว่ายาก ก็คือปัญหา [[อีเอ็กซ์พีบริบูรณ์]] (EXP-complete) (เนื่องมาจาก [[ทฤษฎีลำดับชั้นของเวลา]])
 
== นักวิจัยที่มีชื่อเสียงที่เกี่ยวข้อง ==
* [[:en:Manindra Agrawal]]
* [[:en:Sanjeev Arora]]
* [[:en:Andrew Yao]]
* [[:en:Eugene Yarovoi]]
{{Link FA|de}}
 
[[หมวดหมู่:ทฤษฎีการคำนวณ]]
[[หมวดหมู่:ทฤษฎีความซับซ้อนในการคำนวณ|*]]
 
{{Link FA|de}}
 
[[ar:نظرية التعقيد الحسابي]]
[[fa:نظریه پیچیدگی محاسباتی]]
[[fi:Aikavaativuusluokka]]
[[fr:Théorie de la complexité des algorithmes]]
[[he:סיבוכיות]]
[[hr:Računska teorija složenosti]]
117,007

การแก้ไข