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

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

ภาพรวม

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

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

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

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

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

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

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

ปัญหาการตัดสินใจ

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

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

ค่อนข้างจะชัดเจนว่าเนื้อที่ที่ใช้ในการแก้ปัญหา FACTORIZE จะไม่มากไปกว่าเนื้อที่ที่ใช้ในการแก้ปัญหา HAS-FACTOR นัก (สำหรับค่า ${\displaystyle k}$  แต่ละค่าเราสามารถคืนหน่วยความจำที่ใช้ในการทำงานของค่า ${\displaystyle k}$  ก่อนหน้าได้) สำหรับเวลาที่ใช้ก็เช่นกัน ในการหาตัวประกอบแต่ละตัวเราจะเรียกใช้ HAS-FACTOR ไม่เกิน ${\displaystyle \log(n)}$  ครั้ง และจำนวนของตัวประกอบเฉพาะของ ${\displaystyle n}$  ที่เป็นไปได้ก็ไม่เกิน ${\displaystyle \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) (เนื่องมาจาก ทฤษฎีลำดับชั้นของเวลา)