أو آي تي

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

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

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

الاختصار[عدل]

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

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

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