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