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

ปัญหาการตัดสินใจ () เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม 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 ได้
ยกตัวอย่างเช่น ปัญหาความสอดคล้องแบบบูล เป็นปัญหาที่บริบูรณ์บนกลุ่มปัญหาเอ็นพี และการลดรูปด้วยเวลาเชิงพหุนาม เพราะ ปัญหาความสอดคล้องแบบบูล เป็นสมาชิกของปัญหาเอ็นพี และทุก ๆ ปัญหาเอ็นพี สามารถลดรูป ด้วยเวลาเชิงพหุนาม ไปยังปัญหาความสอดคล้องแบบบูลได้

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