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

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

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

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

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

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

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

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

ทฤษฎีการคำนวณ
ปัญหาทางคณิตศาสตร์