مشكلة اتخاذ القرار

في نظرية الحوسبة ونظرية التعقيد الحسابي ، تُعرَّف مسألة القرار بأنها مسألة حسابية يمكن صياغتها كسؤال إجابته بنعم أو لا على مجموعة من قيم المدخلات. ومن أمثلة مسائل القرار تحديد ما إذا كان عدد طبيعي مُعطى عددًا أوليًا . ومثال آخر هو المسألة: "إذا كان لدينا عددان x و y ، فهل x يقسم y قسمة تامة ؟"

إجراء اتخاذ القرار لمسألة قرار هو أسلوب حسابي يجيب على سؤال بنعم أو لا لجميع المدخلات، وتُسمى مسألة القرار قابلة للتقرير إذا كان هناك إجراء قرار لها. على سبيل المثال، مسألة القرار "بإعطاء عددين س و ص ، هل س يقسم ص بالتساوي ؟" قابلة للتقرير لوجود إجراء قرار يُسمى القسمة المطولة يُحدد خطوات تحديد ما إذا كان س يقسم ص بالتساوي والإجابة الصحيحة، نعم أو لا ، وفقًا لذلك. بعض أهم المسائل في الرياضيات غير قابلة للتقرير ، مثل مسألة التوقف .

يُصنِّف مجال نظرية التعقيد الحسابي مسائل القرار القابلة للحسم وفقًا لمدى صعوبة حلها. ويُعرَّف مصطلح "الصعوبة" هنا من حيث الموارد الحسابية التي يحتاجها الخوارزمية الأكثر كفاءة لحل مسألة معينة. في المقابل، يُصنِّف مجال نظرية الاستدعاء الذاتي مسائل القرار غير القابلة للحسم وفقًا لدرجة تورينج ، وهي مقياس لعدم قابلية أي حل للحساب.

مشكلة القرار هي اللغة الرسمية لجميع المدخلات التي تكون مخرجاتها (الإجابة على سؤال نعم/لا بشأن مدخل معين) هي نعم . ^{[ ملاحظات 1 ]}

• يمكن أن تكون هذه المدخلات أعدادًا طبيعية، ولكن يمكن أن تكون أيضًا قيمًا من نوع آخر، مثل السلاسل الثنائية أو السلاسل المكونة من أبجدية أخرى .

• على سبيل المثال، إذا كان بالإمكان ترميز كل مدخل بواسطة الأبجدية${\displaystyle \{0,1\}}$إذاً، فإن مشكلة القرار هي مجموعة جزئية${\displaystyle L\subseteq \{0,1\}^{*}}$[ ^{ملاحظات 1 ]}

• كمثال آخر، باستخدام ترميز مثل ترقيم غودل ، يمكن ترميز أي سلسلة نصية كعدد طبيعي، ومن خلال ذلك يمكن تعريف مسألة القرار على أنها مجموعة جزئية من الأعداد الطبيعية. وبالتالي، فإن إجراء اتخاذ القرار في مسألة القرار هو حساب الدالة المميزة لمجموعة جزئية من الأعداد الطبيعية.

من الأمثلة الكلاسيكية على مسائل القرار القابلة للحسم مجموعة الأعداد الأولية. فمن الممكن تحديد ما إذا كان عدد طبيعي معين أوليًا عن طريق اختبار كل عامل غير تافه ممكن. ورغم وجود إجراءات أكثر كفاءة لاختبار أولية الأعداد ، فإن وجود أي إجراء فعال يكفي لإثبات قابلية الحسم.

• تكون مسألة القرار قابلة للتقرير أو قابلة للحل بشكل فعال إذا كانت مجموعة المدخلات التي تكون الإجابة عليها "نعم" مجموعة متكررة . ^{[ ملاحظات 2 ]}
• تكون مشكلة القرار قابلة للتقرير جزئياً ، أو شبه قابلة للتقرير ، أو قابلة للحل ، أو قابلة للإثبات إذا كانت مجموعة المدخلات التي تكون الإجابة عليها نعم هي مجموعة قابلة للتعداد بشكل متكرر .

تُسمى المشكلات غير القابلة للحل بالمشكلات غير القابلة للحل ، مما يعني أنه لا يمكن إنشاء خوارزمية (فعّالة كانت أم لا) لحلها. تُعدّ مشكلة التوقف مثالًا مهمًا على المشكلات غير القابلة للحل؛ لمزيد من الأمثلة، راجع قائمة المشكلات غير القابلة للحل .

يمكن ترتيب مسائل القرار وفقًا لإمكانية اختزالها إلى عناصر متعددة، وربطها بالاختزالات الممكنة، مثل الاختزالات التي تتم في زمن متعدد الحدود . يُقال إن مسألة القرار P كاملة لمجموعة مسائل القرار S إذا كانت P عنصرًا من S ، ويمكن اختزال كل مسألة في S إلى P. تُستخدم مسائل القرار الكاملة في نظرية التعقيد الحسابي لتوصيف فئات تعقيد مسائل القرار. على سبيل المثال، تُعد مسألة إرضاء العبارات المنطقية كاملة لفئة NP من مسائل القرار في ظل إمكانية اختزالها في زمن متعدد الحدود.

ترتبط مسائل القرار ارتباطًا وثيقًا بمسائل الدوال ، التي قد تكون إجاباتها أكثر تعقيدًا من مجرد نعم أو لا . ومن أمثلة مسائل الدوال: "إذا كان لدينا عددان x و y ، فما هو ناتج قسمة x على y ؟".

تتكون مسألة الدالة من دالة جزئية f ؛ والمسألة غير الرسمية هي حساب قيم f على المدخلات التي تم تعريفها من أجلها.

يمكن تحويل أي مسألة دالة إلى مسألة قرار؛ ومسألة القرار هي ببساطة تمثيل الدالة المرتبطة بها بيانيًا. (تمثيل الدالة f بيانيًا هو مجموعة الأزواج ( x , y ) التي تحقق f ( x ) = y ). إذا كانت مسألة القرار هذه قابلة للحل فعليًا، فإن مسألة الدالة ستكون كذلك. مع ذلك، لا يراعي هذا الاختزال التعقيد الحسابي. على سبيل المثال، من الممكن أن يكون تمثيل الدالة بيانيًا قابلًا للحل في زمن متعدد الحدود (وفي هذه الحالة، يُحسب زمن التشغيل كدالة للزوج ( x , y )) بينما لا يمكن حساب الدالة نفسها في زمن متعدد الحدود (وفي هذه الحالة، يُحسب زمن التشغيل كدالة لـ x فقط). تتمتع الدالة f ( x ) = 2x ^بهذه الخاصية.

يمكن تحويل أي مسألة قرار إلى مسألة دالة لحساب الدالة المميزة للمجموعة المرتبطة بها. إذا كانت هذه الدالة قابلة للحساب، فإن مسألة القرار المرتبطة بها قابلة للتقرير. مع ذلك، يُعد هذا الاختزال أكثر مرونة من الاختزال القياسي المستخدم في حساب التعقيد الحسابي (والذي يُسمى أحيانًا اختزال متعدد الحدود متعدد الحدود)؛ فعلى سبيل المثال، يكون تعقيد الدوال المميزة لمسألة NP- كاملة ومكملتها co-NP-كاملة متطابقًا تمامًا، حتى وإن لم تُعتبر مسائل القرار الأساسية متكافئة في بعض نماذج الحساب الشائعة.

بخلاف مسائل اتخاذ القرار، التي لا يوجد فيها سوى إجابة صحيحة واحدة لكل مُدخل، فإن مسائل التحسين تُعنى بإيجاد أفضل إجابة لمُدخل مُحدد. وتظهر مسائل التحسين بشكل طبيعي في العديد من التطبيقات، مثل مسألة البائع المتجول والعديد من مسائل البرمجة الخطية .

غالبًا ما تُحوَّل مسائل الدوال والتحسين إلى مسائل قرار من خلال النظر في مسألة ما إذا كان الناتج يساوي أو يقل عن أو يساوي قيمة معينة. يتيح ذلك دراسة تعقيد مسألة القرار المقابلة؛ وفي كثير من الحالات، يمكن حل مسألة الدالة أو التحسين الأصلية بحل مسألة القرار المقابلة لها. على سبيل المثال، في مسألة البائع المتجول، تتمثل مسألة التحسين في إنتاج مسار بأقل وزن ممكن. أما مسألة القرار المرتبطة بها فهي: لكل قيمة N ، تحديد ما إذا كان الرسم البياني يحتوي على أي مسار بوزن أقل من N. من خلال الإجابة على مسألة القرار بشكل متكرر، يمكن إيجاد أقل وزن ممكن للمسار.

نظراً لتطور نظرية مسائل القرار بشكل كبير، فقد ركزت الأبحاث في نظرية التعقيد عادةً على مسائل القرار. ولا تزال مسائل التحسين تحظى باهتمام في نظرية الحوسبة، وكذلك في مجالات أخرى مثل بحوث العمليات .

• الكل (التعقيد)
• مشكلة حسابية
• مسألة العد (التعقيد)
• قابلية الحسم (المنطق) – لمشكلة تحديد ما إذا كانت الصيغة نتيجة لنظرية منطقية .
• اللغة الرسمية
• مشاكل البحث
• مسألة كلامية (رياضيات)

• كوزين، العاصمة (2012). الأتمتة والحوسبة . سبرينغر. رقم ISBN 978-1-4612-1844-9.
• هارتلي، روجرز الابن (1987). نظرية الدوال التكرارية والحوسبة الفعالة . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-262-68052-3.
• سيبسر، م. (2020). مقدمة في نظرية الحوسبة . سينجايج ليرنينج. ISBN 978-0-357-67058-3.
• سواري، روبرت آي. (1987). المجموعات والدرجات القابلة للتعداد بشكل متكرر . سبرينغر. ISBN 0-387-15299-7.
• كرونينج, دانيال ; ستريشمان ، عوفر (23 مايو 2008). إجراءات اتخاذ القرار . سبرينغر. رقم ISBN 978-3-540-74104-6.
• برادلي، آرون؛ مانا، زوهار (3 سبتمبر 2007). حساب التفاضل والتكامل . سبرينغر. ISBN 978-3-540-74112-1.