3-SAT, 3-CNF

Rövid szöveges bemutatás: 
A 3-SAT probléma, egy olyan Boole algebrához tartozó probléma melynek megoldása exponenciálisan nő a formula hosszával. Maga a probléma igen egyszerű: létezik-e a formulában lévő változóknak olyan értékadási módja melyre az egész kifejezés értéke igaz. Legrosszabb esetben végig kell próbálnunk az összes lehetséges igazságérték-hozzárendelést ami n darab bináris változó esetén éppen 2^n lehetséges igazságérték-hozzárendelés. A formula hosszával általában a változók száma is nő, így válik a probléma exponenciálissá. A 3-CNF logikai állítások vagy mondatok, olyan megkötést adnak, hogy egy klózban legfeljebb 3db változó szerepelhet.