The special case of this problem for Horn clauses is P-complete and can be solved by using constraint propagation after having all assignments start as false.
The basis for most modern approaches to this problem is the DPLL algorithm. A nearly identically-posed PSPACE-complete problem is TQBF. By considering a tableau of sequential Turing-machine configurations, the Cook-Levin theorem can be proven, making this the first problem to be demonstrated (*) NP-complete. The special case of this problem for Horn clauses is P-complete and can be solved by using constraint propagation after having all assignments start as false. A variant of this problem with the input in conjunctive-normal-form and three variables per clause is also NP-complete. For 10 points, name this problem of assigning truth-values to variables in a propositional formula such that the formula evaluates to true.
The basis for most modern approaches to this problem is the DPLL algorithm.
Boolean satisfiability [or 3-sat; or k-sat]