مسئله تصمیم

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

مسئله تصمیم

چکیده

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

تعریف

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

تصمیم پذیری

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

مثال‌ها

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

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

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

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

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

${\displaystyle \vdots }$

منابع

Wikipedia contributors, "Decision Problem", Wikipedia, The Free Encyclopedia,

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

پانوشته‌ها

1. An Introduction to the Theory of Computer Science, p. ۳۳
2. Perfect square

منابع

• 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