أو آي تي

مسألة NP كاملة
قابلية الإرضاء 3سات NAE أو آي تي
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

OIT - مسألتان مشتقتان من المسألة العامة لقابلية الارتضاء.

بالضبط واحد من ثلاثة

يعرف اختصارا بOIT وهو عبارة عن صيغة منطقية، تشبه في تكوينها وصيغتها 3SAT والسؤال هو: هل يوجد تعيين قيم للمتغيرات بحيث في كل قوس يكون بالضبط متغير واحد ذو قيمة موجبة؟

الاختصار

يحول $(a\vee b\vee c)$ من 3-سات لصيغة من OIT بإضافة خمس متغيرات جديدة للحصول على صيغة OIT :$(a\vee u\vee v)\wedge (\mathrm{\neg }b\vee u\vee w)\wedge (v\vee w\vee t)\wedge (\mathrm{\neg }c\vee v\vee x)$.

بالضبط واحد من ثلاثة رتيبة

هو عبارة عن مسألة تشبه المسألة أعلاه، الفرق الوحيد هو كون المتغيرات تظهر موجبة أي لا نجد في الصيغة متغيرا ونفي المتغير.