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