أو آي تي

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

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)$ .

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

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

مراجع

بوابة رياضيات
بوابة منطق

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.