Time Complexity

The complexity of 3-SAT Problem is O(2**n).

1. The 3-SAT Problem is a variation of the Satisfiability problem. In the Satisfiability problem, you are given logic expression with N boolean variables, and asked if there is an assignment to these variables that will make the expression return true. The 3-SAT problem restricts the logic expression to or'd clauses of three variables.

2. The Satisfiability is the first algorithm that was proved to be NP-Complete. This is Cook's Theorem.

Reference: Computers and Intractability by M. R. Garey, D. S. Johnson. W. H. Freeman, 1979.