OIT
| مسألة NP كاملة |
|---|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
OIT - هي مسألتين مشتقتين من المسألة العامة لقابلية الارتضاء.
بالضبط واحد من ثلاثة
يعرف اختصارا بOIT و هو عبارة عن صيغة منطقية، تشبه في تكوينها و صيغتها 3SAT و السؤال هو: هل يوجد تعيين قيم للمتغيرات بحيث في كل قوس يكون بالضبط متغير واحد ذو قيمة موجبة؟
الإختصار
يحول خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a\lor b\lor c)} من 3-سات لصيغة من OIT بإضافة خمس متغيرات جديدة للحصول على صيغة OIT :خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a\lor u\lor v)\wedge(\lnot b\lor u\lor w)\wedge(v\lor w\lor t)\wedge(\lnot c\lor v \lor x)} .
بالضبط واحد من ثلاثة رتيبة
هو عبارة عن مسألة تشبه المسألة أعلاه، الفرق الوحيد هو كون المتغيرات تظهر موجبة أي لا نجد في الصيغة متغيرا و نفي المتغير.