OIT
| مسألة NP كاملة |
|---|
|
|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
OIT - هي مسألتين مشتقتين من المسألة العامة لقابلية الارتضاء.
بالضبط واحد من ثلاثة
يعهد اختصارا بOIT وهوتعبير عن صيغة منطقية، تشبه في تكوينها وصيغتها 3SAT والسؤال هو: هل يوجد تعيين قيم للمتغيرات بحيث في جميع قوسقد يكون بالضبط متغير واحد ذوقيمة موجبة؟
الإختصار
يحول
بالضبط واحد من ثلاثة رتيبة
هوتعبير عن مسألة تشبه المسألة أعلاه، الفرق الوحيد هوكون المتغيرات تظهر موجبة أي لا نجد في الصيغة متغيرا ونفي المتغير.
