قابلية الإرضاء

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

تعبر في الرياضيات وفي نظرية التعقيد الحسابي ذات أهمية كبيرة جدا.

الصيغة العادية لعطف عبارات مكونة من فصل المتغيرات

هي عبارة عن صيغة عناصرها متغيرات تقبل فقط القيم صحيح خطأ 0 1 لا نعم موزعة على أقواس وتستعمل العمليات المنطقية عطف وفصل ونفي كما في هذا المثال: $(a\vee \mathrm{\neg }b\vee c)\wedge (a\vee b\vee \mathrm{\neg }d)\wedge (a\vee c\vee e)\wedge (b\vee d\vee \mathrm{\neg }e)$.

جعل الصيغة صحيحة

المسألة الخاصة هو البحث عن قيم المتغيرات بحيث تكون الصيغة صحيحة يعني أن كل قوس يجب أن يكون صحيحا يعني أن يكون هناك على الأقل متغير في كل قوس له القيمة 1 نعم صحيح.

محاولة تجريب كل الاحتمالات الممكنة يحتاج لوقت أسي $O(c^n)$.

ملف:Nuvola apps edu mathematics-ar.svg

بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات.

de:Erfüllbarkeitsproblem der Aussagenlogik Boolean satisfiability problem]] es:Problema de satisfacibilidad booleana he:SAT ja:充足可能性問題 pl:Problem spełnialności th:ปัญหาความสอดคล้องแบบบูล