3SAT
3SAT Problem
Gleiches Entscheidungsproblem wie bei SAT bloß mit einer Einschränkung der erlaubten Ausdrücke. Es werden höchstens 3 Literale pro Klausel erlaubt.
Als Sprache formuliert:
$$\mathrm{3SAT} = \left\{\langle\phi\rangle\mid \phi\text{ ist eine erfüllbare }\textrm{KNF} \text{ mit $3$ Literalen pro Klausel} \right\}$$