[Overview] [Previous] [Next]

Boolean Satisfiability

Suppose you have n Boolean variables, named A, B, C, ..., and you have an expression in the propositional calculus (that is, you can use and, or, and not to form the expression.) Is there an assignment of truth values to the variables (e.g. A=true, B=true, C=false, ....) that will make the expression true?

Here is a nondeterministic algorithm to solve the problem: For each Boolean variable, assign it the proper truth value. This is a linear algorithm.

We can find a deterministic algorithm for this problem in much the same way as we did for the integer bin problem. Effectively, the idea is to set up a systematic procedure to try every possible assignment of truth values to variables. The algorithm terminates when a satisfactory solution is found, or when all 2n possible assignments have been tried. Again, the deterministic solution requires exponential time.

Problems such as this arise in circuit design.

Copyright 1996 by David Matuszek
Last modified Apr 28, 1996