The complexity of satisfiability problems

Abstract

The problem of deciding whether a given propositional formula in conjunctive normal form is satisfiable has been widely studied. I t is known that, when restricted to formulas having only two literals per clause, this problem has an efficient (polynomial-time) solution. But the same problem on formulas having three literals per clause is NP-complete, and hence probably does not have any efficient solution.