alul-határozott probléma

Kapcsolódó fogalmak: 
3-SAT, 3-CNF
Kapcsolódó könyvfejezetek: 
7.5. Hatékony ítéletkalkulus következtetés
Rövid szöveges bemutatás: 
Alul-határozott az amikor a lehetséges hozzárendelések közül nagyon sok megoldás helyes, és bármely kezdeti hozzárendeléshez találunk egy megoldást a közelben. Az n-királynő probléma például alul-határozott. Amikor konjunktív normál formában lévő kielégíthetőségi problémákat vizsgálunk, akkor azt alul-határozott problémának nevezzük, hogyha kevés a változómegkötés. Például: (¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C). 5 változó szerepel, tehát összesen 2^5=32 a lehetséges hozzárendelések száma, és 16 kielégíti a mondatot. Tehát átlagosan két próbálkozás után megoldható a feladat.