قابلية الإرضاء
| مسألة NP كاملة |
|---|
|
|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
تعبر في الرياضيات وفي نظرية التعقيد الحسابي ذات أهمية كبيرة جدا.
الصيغة العادية لعطف عبارات مكونة من فصل المتغيرات
هي تعبير عن صيغة عناصرها متغيرات تقبل فقط القيم سليم خطأ 0 1 لا نعم موزعة على أقواس وتستعمل العمليات المنطقية عطف وفصل ونفي كما في هذا المثال: .
جعل الصيغة سليمة
المسألة الخاصة هوالبحث عن قيم المتغيرات بحيث تكون الصيغة سليمة يعني حتى جميع قوس يجب حتىقد يكون سليما يعني حتىقد يكون هناك على الأقل متغير في جميع قوس له القيمة 1 نعم سليم.
محاولة تجريب جميع الاحتمالات الممكنة يحتاج لوقت أسي .
