3-SAT

← Back to NP-Complete

A restricted form of SAT where the Boolean formula is in conjunctive normal form with exactly 3 literals per clause. Still NP-Complete despite the restriction. Commonly used as the starting point for reductions proving other problems NP-Complete.

computational-complexity complexity-classes np-complete 3-sat