সিদ্ধান্ত সমস্যা

গণনীয়তা তত্ত্ব এবং গণনামূলক জটিলতা তত্ত্বে সিদ্ধান্ত সমস্যা (ইংরেজি: Decision problem) বলতে কোন একটি বিধিবদ্ধ ব্যবস্থায় (formal system) অবস্থিত এমন একটি প্রশ্নকে বোঝায়, ইনপুট করা পরামিতিগুলির উপর ভিত্তি করে যে প্রশ্নের উত্তর হ্যাঁ বা না হতে পারে।

সিদ্ধান্ত সমস্যা

উদাহরণস্বরূপ, "প্রদত্ত দুইটি সংখ্যা x এবং y-এর জন্য x কি y-কে নিঃশেষে ভাগ করে?" সমস্যাটি একটি সিদ্ধান্ত সমস্যা। x এবং y-এর মানের উপর নির্ভর করে প্রশ্নটির উত্তর "হ্যাঁ" হবে, না কি "না" হবে।

সিদ্ধান্ত সমস্যাগুলি ফাংশন সমস্যাগুলির সাথে ঘনিষ্ঠ সম্পর্কযুক্ত, তবে ফাংশন সমস্যাগুলির উত্তর কেবল হ্যাঁ/না-তে সীমাবদ্ধ নয়। এছাড়া এগুলি অপ্টিমাইজেশন সমস্যা-র সাথেও সম্পর্কিত, যেগুলিতে কোন একটি সমস্যার সবচেয়ে ভাল সমাধান বের করার চেষ্টা করা হয়।