OIT

مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

الإختصار

يحول من 3-سات لصيغة من OIT بإضافة خمس متغيرات جديدة للحصول على صيغة OIT :.

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

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