OIT

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

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

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

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

الإختصار

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

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

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