ทฤษฎีความซับซ้อนในการคำนวณ - วิกิพีเดีย

# ทฤษฎีความซับซ้อนในการคำนวณ

### จากวิกิพีเดีย สารานุกรมเสรี

| บทความนี้มีลิงก์แทรกในบทความที่ข้ามไปภาษาอื่นโดยเป็นลิงก์สีฟ้าอ่อน โดยผู้เขียนใส่ไว้เพื่อสะดวกในการเขียน และควรแก้ลิงก์ภาษาอื่นเป็นข้อความธรรมดา เมื่อมีลิงก์ภาษาไทยที่ถูกต้อง หรือเห็นควร เพื่อไม่ให้ผู้อ่านสับสน

ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของ ทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า). ในบางกรณีเราอาจจะสนใจการวิเคราะห์ปริมาณอื่น ๆ ที่นอกเหนือไปจากพื้นที่กับเวลา ยกตัวอย่างเช่น ในการประมวลผลแบบขนาน เราอาจจะวิเคราะห์ว่าต้องใช้หน่วยประมวลผลกี่ตัวในการแก้ปัญหาที่กำหนด. ทฤษฎีความซับซ้อนต่างจาก ทฤษฎีการคำนวณได้ ที่จะเน้นไปในการวิเคราะห์ว่าปัญหาสามารถแก้ได้หรือไม่ โดยไม่สนใจทรัพยากรที่ใช้ในการแก้ปัญหา

## [แก้] ภาพรวม

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

ในที่นี้ เราจะมอง "ปัญหา" หนึ่ง ๆ ว่าเป็นเซตของคำถามที่เกี่ยวข้องในปัญหานั้นทั้งหมด โดยแต่ละคำถามจะเป็นสตริงที่มีความยาวจำกัด ยกตัวอย่างเช่น ปัญหา แยกตัวประกอบ (FACTORIZE) คือ:

  ให้เลขจำนวนเต็มหนึ่งตัวที่เขียนอยู่ในรูปของเลขฐานสอง เราต้องการเขียนตัวเลขนี้ให้อยู่ในรูปผลคูณของจำนวนเฉพาะ

คำถามใดๆ คำถามหนึ่งจะถูกเรียกว่า "ตัวอย่างปัญหา" (instance) ในกรณีนี้ เราจะเรียก "จงหาตัวประกอบที่เป็นจำนวนเฉพาะของ 15" ว่าเป็นตัวอย่างปัญหาของปัญหาแยกตัวประกอบ

เราจะนิยาม ความซับซ้อนด้านเวลา (time complexity) สำหรับปัญหาหนึ่ง ๆ ว่าเป็นจำนวนขั้นตอนที่ใช้ในการแก้ตัวอย่างปัญหาสำหรับปัญหานั้น ในรูปฟังก์ชันของขนาดของข้อมูลป้อนเข้า (ซึ่งโดยปกติแล้วเราจะคิดขนาดเป็นบิต) โดยใช้ขั้นตอนวิธีที่มีประสิทธิภาพที่สุด ยกตัวอย่างเช่น ในปัญหา ๆ หนึ่ง สำหรับทุกตัวอย่างปัญหาที่มีขนาด n บิต ถ้าเราสามารถแก้ตัวอย่างปัญหานี้ได้ภายใน n2 ขั้นตอน เราสามารถพูดได้ว่าปัญหานี้มีความซับซ้อนด้านเวลาเป็น n2 ซึ่งในการกล่าวถึงเวลาที่ใช้นั้น แน่นอนว่าเครื่องจักร หรือ คอมพิวเตอร์แต่ละเครื่องก็ใช้เวลาในการคำนวณแตกต่างกันไป เพื่อที่จะหลีกเลี่ยงความแตกต่างในจุดนี้ เราจะใช้สัญกรณ์โอใหญ่ (Big O notation) ปัญหาที่มีความซับซ้อนด้านเวลาเป็น O(n2) ในเครื่องคอมพิวเตอร์เครื่องหนึ่ง จะมีความซับซ้อนด้านเวลาเป็น O(n2) บนเครื่องอื่นๆด้วยเช่นกัน จะเห็นได้ว่าสัญกรณ์โอใหญ่ช่วยเราหลีกเลี่ยงการกล่าวถึงรายละเอียด ที่เป็นความแตกต่างระหว่างเครื่องคอมพิวเตอร์

หลายครั้งเราจะกล่าวถึงความซับซ้อนด้านเวลาว่าเป็น "เวลาที่ใช้ในการแก้ปัญหา" หรือ "เวลาที่ใช้ในการทำงาน"

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

## [แก้] ปัญหาการตัดสินใจ

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

ปกติแล้ว ปัญหาการตัดสินใจมักจะเป็นที่สนใจเพราะว่า ปัญหาหลายปัญหามักจะสามารถลดรูปไปเป็นปัญหาในกลุ่มนี้ได้. ยกตัวอย่างเช่น ปัญหา HAS-FACTOR ที่ถามว่า สำหรับจำนวนเต็ม n และ k, จำนวน n มีตัวประกอบเฉพาะที่มีค่าไม่เกิน k หรือไม่? ในที่นี้เราจะแสดงให้เห็นว่า การแก้ปัญหา HAS-FACTOR จะนำไปสู่การแก้ปัญหา FACTORIZE ที่เราได้กล่าวถึงไปแล้ว โดยใช้ทรัพยากรไม่มากกว่ากันนัก สังเกตว่าหากเราสามารถแก้ปัญหา HAS-FACTOR ได้ เราสามารถใช้การค้นหาแบบทวิภาค (binary search) เพื่อหาค่าของ k ที่น้อยที่สุดที่เป็นตัวประกอบของ n และเมื่อเจอจำนวนนั้นแล้ว เราก็จะหารมันทิ้งไป ทำซ้ำไปเรื่อย ๆ จนกระทั่งไม่สามารถทำต่อได้ เราก็จะสามารถหาตัวประกอบเฉพาะทั้งหมดของ n ออกมาได้

ค่อนข้างจะชัดเจนว่าเนื้อที่ที่ใช้ในการแก้ปัญหา FACTORIZE จะไม่มากไปกว่าเนื้อที่ที่ใช้ในการแก้ปัญหา HAS-FACTOR นัก (สำหรับค่า k แต่ละค่าเราสามารถคืนหน่วยความจำที่ใช้ในการทำงานของค่า k ก่อนหน้าได้) สำหรับเวลาที่ใช้ก็เช่นกัน ในการหาตัวประกอบแต่ละตัวเราจะเรียกใช้ HAS-FACTOR ไม่เกิน log(n) ครั้ง และจำนวนของตัวประกอบเฉพาะของ n ที่เป็นไปได้ก็ไม่เกิน log(n) จำนวน

ในศาสตร์ของทฤษฎีความซับซ้อนของปัญหานั้น ตัวอย่างของปัญหาที่มีคำตอบเป็น "ใช่" มักจะมีความแตกต่างจากตัวอย่างของปัญหาที่มีคำตอบเป็น "ไม่ใช่" เช่น กลุ่มปัญหาเอ็นพี (NP) ประกอบด้วยปัญหาการตัดสินใจทั้งหมดที่ตัวอย่างปัญหาที่มีคำตอบเป็น "ใช่" สามารถตรวจสอบได้อย่างมีประสิทธิภาพ และในทางกลับกัน กลุ่มปัญหาโค-เอ็นพี (co-NP) ประกอบด้วยปัญหาการตัดสินใจที่ตัวอย่างของปัญหาที่มีคำตอบเป็น "ไม่ใช่" สามารถตรวจสอบได้อย่างมีประสิทธิภาพ (คำว่า co ในที่นี้หมายถึง ส่วนกลับ หรือ complement) ซึ่งส่วนกลับของปัญหาหนึ่งก็คือปัญหาเดิมที่มีการสลับตัวอย่างปัญหาที่มีคำตอบคือ "ใช่" กับตัวอย่างปัญหาที่มีคำตอบคือ "ไม่ใช่" ตัวอย่างเช่นปัญหา "IS-PRIME" เป็นส่วนกลับของปัญหา "IS-COMPOSITE"

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

## [แก้] กลุ่มของความซับซ้อนของปัญหา

ปัญหาการตัดสินใจสามารถแบ่งออกได้เป็นหลายๆกลุ่ม โดยที่แต่ละกลุ่มจะประกอบไปด้วยปัญหาที่มีความยากเท่าเทียมกัน

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

กลุ่มความซับซ้อนของปัญหา เอ็นพี (NP) คือเซตของปัญหาการตัดสินใจที่สามารถแก้ปัญหาได้โดยใช้เครื่องจักรทัวริงเชิงไม่กำหนดในเวลาพหุนาม ปัญหาที่อยู่ในกลุ่มนี้หลายปัญหาเป็นปัญหาที่มนุษย์ต้องการเป็นอย่างมากที่จะแก้ให้ได้อย่างมีประสิทธิภาพ ตัวอย่างของปัญหาในกลุ่มนี้ก็คือ ปัญหาความสอดคล้องแบบบูล (Boolean satisfiability problem) ปัญหาเส้นทางของฮามิลตัน (Hamiltonian path problem) และ ปัญหาจุดยอดปกคลุม (Vertex cover problem) ปัญหาทุกปัญหาในกลุ่มนี้สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ

## [แก้] ปัญหา P=NP

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

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

สำหรับหลักการของ ความบริบูรณ์นั้น เราจะกล่าวว่าเซต X บริบูรณ์ สำหรับเซต Y เมื่อ:

- เซต X ยาก สำหรับ Y และ
- X เป็นเซตย่อยของ Y

เช่นเดียวกันกับเรื่องของความยาก เซตบริบูรณ์ที่สำคัญที่สุดก็คือ เซตเอ็นพีบริบูรณ์

## [แก้] ความยาก (Intractability)

เราเรียกปัญหาที่สามารถหาคำตอบได้ ในเชิงทฤษฎี แต่ไม่สามารถนำมาใช้ได้จริง ว่าเป็นปัญหาที่ยาก (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

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%97/%E0%B8%A4/%E0%B8%A9/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%84%E0%B8%A7%E0%B8%B2%E0%B8%A1%E0%B8%8B%E0%B8%B1%E0%B8%9A%E0%B8%8B%E0%B9%89%E0%B8%AD%E0%B8%99%E0%B9%83%E0%B8%99%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%84%E0%B8%B3%E0%B8%99%E0%B8%A7%E0%B8%93.html".

หมวดหมู่: บทความที่มีลิงก์ไปภาษาอื่นในส่วนเนื้อหา | ทฤษฎีการคำนวณ | ทฤษฎีความซับซ้อนในการคำนวณ

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Česky
- Deutsch
- Ελληνικά
- English
- Español
- Français
- עברית
- Italiano
- 日本語
- 한국어
- Lietuvių
- Nederlands
- Polski
- Português
- Svenska
- 中文