Propositional Logic & NP-Completeness

One interesting "application" of propositional logic in computer science is the problem sometimes known as the "Boolean satisfiability problem", or "SAT".
(No, it has nothing to do with the S.A.T. exams!)

It's called "Boolean", after George Boole, one of the first modern logicians to study two-valued logic.
(He is the author of a book called The Laws of Thought; there's a biography of him on p.5 of the Rosen text;
see also amazon.com and an online article by him: Boole, George (1848), "The Calculus of Logic", Cambridge and Dublin Mathematical Journal 3: 183–198).

And it's called "satisfiability", because it concerns how to determine whether a compound proposition has the truth value T given the truth values of its atomic propositions.

Recall from class that, if a compound proposition is constructed from n atomic propositions,
then its truth table requires 2ⁿ rows, which grows exponentially large, i.e., very quickly.

As you may know, not all problems are solvable by computer (i.e., "are computable").
The most famous noncomputable problem is the "Halting Problem":

To write a computer program that takes as input any computer program and outputs "yes" if its input halts and "no" if its input has an infinite loop in it.

But among computable problems, some can be solved in a reasonable amount of time and others can't.
The theory of computational complexity studies the efficiency of computer programs.
The ones that can be solved in a reasonable amount of time are said to be solvable in "polynomial time";
the others are said to be solvable only in "non-deterministic polynomial time",
which—without going into any details—comes down to saying that they can't be solved before the universe ends, more or less.

Now, it turns out that some of these problems are "NP-complete", which means that

1. as far as we know, they can only be solved in NP (Non-deterministic Polynomial time), and

2. if any of them can also be solved in P (Polynomial time), then all of them can.

The most famous NP-complete problem is SAT.

In other words, if you can prove that you can write a computer program that will compute any truth table in polynomial time,
then all programs are capable of being solved in "reasonable" time.

But don't get your hopes up:

No one knows if the set of NP problems is equal to the set of P problems.
If it isn't, then it's highly unlikely that SAT is a P problem.

For more details, see:

1. Lindley, David (2008), "The Limits of Computability", Communications of the ACM 51(11) (November): 17-19.
   • A non-technical article telling how "computational complexity and intractability may help scientists better understand how humans process information and make decisions".

2. Wikipedia contributors, "Boolean satisfiability problem", Wikipedia, The Free Encyclopedia (accessed January 29, 2008).

3. Wikipedia contributors, "NP-complete", Wikipedia, The Free Encyclopedia (accessed January 29, 2008).