مسئله تصمیم

به زبان صوری، مسئله تصمیم (Decision problem) در نظریهٔ محاسبات به مجموعه‌ای از سؤالات مربوط به‌هم اطلاق می‌شود، به‌طوری که هر یک از پرسش‌ها جواب بلی یا خیر داشته باشد.

چکیده

در نظریه شمارش و همچنین پیچیدگی محاسباتی، مساله تصمیم گیری، سوالی با پاسخ بله یا خیر می‌باشد که به ورودی بستگی دارد.برای مثال در مساله "با داشتن X و Y آیا X بر Y بخشپذیر است"یک مساله تصمیم گیری است.که جواب آن میتواند بله یا خیر بر اساس مقادیر X و Y باشد. روشی که به شکل الگوریتم برای حل یک مساله تصمیم گیری ارائه می‌شود فرایند تصمیم گیری برای آن مساله نامیده می شود.فرایند تصمیم گیری برای مساله"با داشتن X و Y آیا X بر Y بخشپذیر است؟"شامل گام‌های لازم برای مشخس کردن این است که آیا X بر Y تقسیم می‌شود یا خیر.الگوریتم به کار رفته در این مساله تقسیم است، اگر باقی مانده صفر شودجواب مثبت است در غیر اینصورت خیر.به سوالی که با الگوریتم قابل حل باشد تصمیم پذیرمی گویند.

تعریف

مساله تصمیم گیری هر سوال دلخواه بله یا خیر است که ورودی‌های محدود دارد.به همین خاطر، به صورت سنتی مساله تصمیم گیری به شکل زیر تعریف میشود: مجموعه از ورودی‌ها که بازای آن‌ها خروجی مساله "بله"می شود. این ورودی‌ها میتوانند اعداد طبیعی باشند همچنین رشته‌های یک زبان که با نوعی کد گذاری خاص قابل تبدیل به اعداد طبیعی هستند.بنابرین به صورت غیر رسمی، مساله تصمیم گیری هم ارزبا مجموعه اعداد طبیعی در نظر گرفته می شود.برای ساده سازی تعریف رسمی، آنرا به صورت زیر مجموعه از اعداد طبیعی بازگو می کنیم.بنابرین مساله تصمیم گیری معادل این است که آیا عدد داده شده در زیر مجموعه وجود دارد یا نه؟

تصمیم پذیری

مساله A تصمیم پذیر یا قابل حل نامیده می شود، اگر A مجموعه بازگشتی شمارا باشد (یعنی بتوان به ازای متناهی عمل تصمیم گرفت که آیا عدد مورد نظر به مجموعه تعلق دارد یا نه؟) یک مسالهقسمتی تصمیم پذیر یا قابل اثبات نامیده می‌شود اگر الگوریتمی وجود داشته باشد که اعضا مجموعه مورد نظر را بشمارد، حتی اگر باری همیشه این کار ادامه یابد.به مسائل قابل اثبات یا دیگر مسائل تصمیم ناپذیرگویند.

مثال‌ها

یک نمونه کلاسیک از این نوع مساله، مجموعه اعداد ا اول میباشد، از آنجا که به سادگی قابل تصمیم گیری است که آیا یک عدد طبیعی اول می‌باشد یا نه؟(با تقسیم کردن آن بر عوامل اول)هرچند برای تشخیص اول بودن الگوریتم‌های کارآمد تری موجود است، وجود یک روش برای حل مساله تصمیم گیری کافی است.

مسئلهٔ تصمیم‌گیری در مورد مربع کامل بودن یک عدد طبیعی داده شده را می‌شود به‌صورت زیر مطرح نمود:

مسئله ۰ : آیا ۰ یک مربع کامل است؟

مسئله ۱ : آیا ۱ یک مربع کامل است؟

مسئله ۲ : آیا ۲ یک مربع کامل است؟

$\vdots$

منابع

Wikipedia contributors, «Decision Problem», Wikipedia, The Free Encyclopedia,

http://en.wikipedia.org/wiki/Decision_problem

منابع

• Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5 [۱]