For example, the 3-satisfiability problem, a restriction of the boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, NL-complete), and the slightly more general max.
De exemplu, problema 3-satisfiabilității⁠(d) problema, o restrângere a problemei satisfiabilității booleene, rămâne NP-completă, pe când problema ușor mai restrânsă a 2-satisfiabilității⁠(d) este în P (în special, NL-completă⁠(d)), iar problema mai generală, max.