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

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

มุมมองต่อปัญหาการตัดสินใจ

ในมุมมองของภาษารูปนัย ปัญหาการตัดสินใจสามารถมองเป็น ปัญหาสมาชิก (member problem) ได้ โดยมองว่าปัญหาการตัดสินใจเป็นการพิจารณาว่าอินพุตที่เข้ามาเป็นสมาชิกของ (membership) เซตหรือไม่? หรือเป็นสมาชิกของ ภาษาหรือไม่ ยกตัวอย่างเช่น กำหนดให้ P1 แทนปัญหาที่ว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม่ ถ้าเราให้ Prime เป็นเซตของจำนวนเฉพาะ เราก็สามารถเปลี่ยนปัญหา P เป็นปัญหาสมาชิกได้ว่า P1 จำนวนเต็ม x เป็นสมาชิกของเซต Prime หรือไม่ นั่นเอง

เรายังสามารถมองปัญหาบนจำนวนเต็มใดๆ เป็นปัญหาการตัดสินใจจำนวนอนันต์แบบนับได้ได้เช่น กำหนดให้ P2 แทนปัญหาที่ถามว่าจำนวนเต็ม xมีตัวประกอบเฉพาะจำนวนกี่ตัว เราก็สามารถใช้ปัญหาการตัดสินใจช่วยโดยการไล่ถามบนเซตของจำนวนเต็มว่า

1. จำนวนเต็ม x มีตัวประกอบเฉพาะ จำนวน 1 ตัวใช่หรือไม่
2. จำนวนเต็ม x มีตัวประกอบเฉพาะ จำนวน 2 ตัวใช่หรือไม่
3. จำนวนเต็ม x มีตัวประกอบเฉพาะ จำนวน 3 ตัวใช่หรือไม่
4. จำนวนเต็ม x มีตัวประกอบเฉพาะ จำนวน 4 ตัวใช่หรือไม่

...

ถ้าไล่ถามแล้วพบว่าข้อใดตอบว่าใช่ เราก็สามารถตอบได้ว่าจำนวนเต็มดังกล่าวเป็นคำตอบของปัญหา P2

การตัดสินได้และการรับรองได้

การพิจารณาว่าปัญหาการตัดสินใจหนึ่งๆ เป็นปัญหาที่แก้ได้หรือไม่เป็นประเด็นที่สำคัญในทฤษฎีการคำนวณได้ ทฤษฎีการคำนวณได้ จึงได้นิยามศัพท์คำว่า การตัดสินได้ และ การรับรองได้ โดยนิยามไว้ดังนี้

• ปัญหาที่ ตัดสินได้ (decidable) แก้ได้ (solvable) หรือ รู้จำได้ (recognizable) หมายถึงปัญหาที่มีเครื่องจักรทัวริงที่สามารถตอบปัญหานี้ได้ว่า "ใช่" หรือ "ไม่ใช่" เสมอสำหรับทุกๆ อินพุต ปัญหานี้จะมีความสัมพันธ์กับ recursive set
• ปัญหาที่ รับรองได้ (acceptable) หมายถึงปัญหาที่มีเครื่องจักรทัวริงที่สามารถตอบปัญหานี้ได้ว่า "ใช่" เสมอสำหรับอินพุตที่ "ใช่" แต่สำหรับอินพุตที่ "ไม่ใช่" เครื่องจักรทัวริง อาจตอบว่า "ไม่ใช่" หรือทำงานไปเรื่อยๆ โดยไม่สิ้นสุดก็ได้ ปัญหานี้จะมีความสัมพันธ์กับ recursively enumerable set
• ปัญหาที่ ตัดสินไม่ได้ (undecidable) หมายถึงปัญหาการตัดสินใจอื่นๆ ที่ไม่ใช่ ปัญหาที่ตัดสินได้

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

ความบริบูรณ์ของปัญหา

การพิจารณาว่าปัญหาการตัดสินใจหนึ่งๆ เป็นปัญหาที่มีความซับซ้อนอย่างไรเมื่อเทียบกับปัญหาการตัดสินใจอื่นๆ เป็นประเด็นที่สำคัญในทฤษฎีความซับซ้อนในการคำนวณ ทฤษฎีความซับซ้อนในการคำนวณ จึงได้นิยามศัพท์คำว่าความบริบูรณ์ของปัญหา โดยนิยามว่า

ปัญหาการตัดสินใจ P ใดๆ เป็นปัญหาที่บริบูรณ์ (complete) บนเซตของปัญหาการตัดสินใจ S และการลดรูปแบบ ${\displaystyle {\mathcal {R}}}$  ก็ต่อเมื่อ

1. P เป็นสมาชิกของ S
2. ทุกๆ ปัญหาที่เป็นสมาชิกของ S สามารถลดรูป แบบ ${\displaystyle {\mathcal {R}}}$  ไปยังปัญหา P ได้

ยกตัวอย่างเช่น ปัญหาความสอดคล้องแบบบูล เป็นปัญหาที่บริบูรณ์บนกลุ่มปัญหาเอ็นพี และการลดรูปด้วยเวลาเชิงพหุนาม เพราะ ปัญหาความสอดคล้องแบบบูล เป็นสมาชิกของปัญหาเอ็นพี และทุกๆ ปัญหาเอ็นพี สามารถลดรูป ด้วยเวลาเชิงพหุนาม ไปยังปัญหาความสอดคล้องแบบบูลได้