From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Mon Jan 28 19:59:08 2008 Date: Mon, 28 Jan 2008 19:58:54 -0500 From: "William J. Rapaport" Subject: PROPOSITIONAL LOGIC & NP-COMPLETENESS To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU Status: RO Content-Length: 2949 ------------------------------------------------------------------------ Subject: 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 (I mentioned him in lecture as the author of a book called "The Laws of Thought"; there's a biography of him on p.5 of the Rosen text). 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^n 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 **un**computable 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. No such program can exist. (Think of the barber...) But among **computable** problems, some can be solved in a reasonable amount of time and others can't. The theory of computational complexity studies how efficient computer programs are. 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 (a) as far as we know, they can only be solved in NP (Non-deterministic Polynomial time) and (b) 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: Wikipedia contributors, "Boolean satisfiability problem," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Boolean_satisfiability_problem&oldid=179501425 (accessed January 29, 2008). Wikipedia contributors, "NP-complete," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=NP-complete&oldid=186418431 (accessed January 29, 2008).