În informatică teoretică , mai exact în teoria complexității , problema 3-SAT este o problemă utilizată în principal pentru a demonstra că alte probleme sunt NP-hard. Aceasta este una dintre cele 21 de probleme NP-complete ale lui Karp .
Aceasta este restricția problemei SAT la formule care sunt forme normale conjunctive cu cel mult 3 litere (sau exact 3 în funcție de surse). Iată un exemplu de astfel de formă normală conjunctivă:
Formula de mai sus are 4 clauze, 5 variabile și trei litere per clauză. Este vorba de a determina dacă se poate atribui o valoare Adevărată sau Falsă fiecărei variabile pentru a face întreaga formulă adevărată.
În 1972, Richard M. Karp a redus SAT la 3-SAT pentru a demonstra că 3-SAT este NP-hard. Această dovadă este prezentă în multe lucrări despre algoritmi și teoria complexității.
Deoarece 3-SAT este NP-hard, 3-SAT a fost folosit pentru a demonstra că alte probleme sunt NP-hard. Richard M. Karp, în același articol, arată că problema colorării graficului este NP-hard prin reducerea acesteia la 3-SAT în timp polinomial.
Jan Kratochvil a introdus în 1994 o așa-numită restricție plană 3-SAT, care este, de asemenea, dificilă pentru NP. Aceasta este restricția 3-SAT în care graficul bipartit compus din variabile și clauze, unde o variabilă este legată de o clauză dacă această clauză conține această variabilă, este plan. În plus, problema este întotdeauna NP-hard dacă fiecare clauză conține 3 litere și fiecare variabilă apare în cel mult 4 clauze.
nu-toate-egale 3-satisfacție ( NAE3SAT ) este varianta în care cerem ca cele trei variabile dintr-o clauză să nu aibă toate aceeași valoare de adevăr.