المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.
يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.
يرجى مراجعة هذه المقالة وإزالة وسم المقالات غير المراجعة، ووسمها بوسوم الصيانة المُناسبة.

أو آي تي

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)
N write.svg
هذه مقالة جديدة غير مُراجعة. ينبغي أن يُزال هذا القالب بعد أن يُراجعها محررٌ ما عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المُناسبة. (يونيو 2007)
Arwikify.svg
هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (مارس 2015)
مسألة 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).

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

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