مشكلة الوعد

في نظرية التعقيد الحسابي ، تُعدّ مسألة الوعد تعميمًا لمسألة القرار ، حيث يُضمن انتماء المُدخل إلى مجموعة فرعية مُحددة من جميع المُدخلات المُمكنة. ^{[ 1 ]} على عكس مسائل القرار، فإنّ حالات "نعم" (المُدخلات التي يجب على الخوارزمية أن تُرجع "نعم" ) وحالات "لا" لا تُغطي جميع المُدخلات. وبشكلٍ بديهي، يُضمن للخوارزمية أن المُدخل ينتمي بالفعل إلى مجموعة حالات "نعم" أو حالات "لا" . قد توجد مُدخلات ليست "نعم" ولا "لا" . إذا تم إعطاء مثل هذا المُدخل لخوارزمية لحل مسألة وعد، يُسمح للخوارزمية بإخراج أي شيء، وقد لا تتوقف حتى.

يمكن ربط مشكلة اتخاذ القرار بلغة معينة.${\displaystyle L\subseteq \{0,1\}^{*}}$، حيث تكمن المشكلة في قبول جميع المدخلات في${\displaystyle L}$ورفض جميع المدخلات غير الموجودة في${\displaystyle L}$بالنسبة لمسألة الوعد، توجد لغتان،${\displaystyle L_{\text{YES}}}$و${\displaystyle L_{\text{NO}}}$، والتي يجب أن تكون منفصلة ، مما يعني${\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing }$بحيث تكون جميع المدخلات في${\displaystyle L_{\text{YES}}}$يجب قبول جميع المدخلات${\displaystyle L_{\text{NO}}}$يجب رفضها. المجموعة${\displaystyle L_{\text{نعم}}\cup L_{\text{لا}}}$يُطلق على هذا اسم الوعد . لا توجد متطلبات على المخرجات إذا لم يكن المدخل جزءًا من الوعد. إذا كان الوعد يساوي${\displaystyle \{0,1\}^{*}}$إذاً، فهذه أيضاً مشكلة قرار، ويُقال إن الوعد تافه.

العديد من المشكلات الطبيعية هي في الواقع مشكلات وعد. على سبيل المثال، لننظر في المشكلة التالية: بالنظر إلى رسم بياني موجه غير دوري ، حدد ما إذا كان الرسم البياني يحتوي على مسار طوله 10. الحالات التي تكون فيها الإجابة "نعم" هي رسوم بيانية موجهة غير دورية تحتوي على مسار طوله 10، بينما الحالات التي تكون فيها الإجابة "لا" هي رسوم بيانية موجهة غير دورية لا تحتوي على مسار طوله 10. الوعد هو مجموعة الرسوم البيانية الموجهة غير الدورية. في هذا المثال، يسهل التحقق من الوعد. على وجه الخصوص، من السهل جدًا التحقق مما إذا كان الرسم البياني المعطى دوريًا. ومع ذلك، قد يكون تقييم الخاصية الموعودة صعبًا. على سبيل المثال، لننظر في المشكلة "بالنظر إلى رسم بياني هاميلتوني ، حدد ما إذا كان الرسم البياني يحتوي على دورة بحجم 4". الآن، يُعد تقييم الوعد مسألة صعبة من نوع NP ، ومع ذلك فإن حل مشكلة الوعد سهل لأن التحقق من الدورات بحجم 4 يمكن إجراؤه في وقت متعدد الحدود .

• مشكلة حسابية
• مشكلة اتخاذ القرار
• مشكلة التحسين
• مشاكل البحث
• مسألة العد (التعقيد)
• مشكلة دالة
• TFNP