Admin:
If I cannot mark hw1 by Thursday night, I'll delay hw3!
EUMMA career event today, 5:30pm in PAIS 290
Usual office hours today and tomorrow.
Lecture:
Last time we say that various problems (CLIQUE, VC, HAMPATH, SAT),
by the "guess and check" method:
SAT = { : phi is a boolean formula and phi is satisiable }
We also defined P-reductions: these are like mapping reductions,
except the reducing function f is computable in polynomial time.
Today:
Easy: We define "NP-hard" and "NP-complete".
Hard: We prove that SAT is NP-complete!
This last claim is the heart of the chapter, and is known as the
Cook-Levin theorem (two independent proofs).
I won't repeat much of the steps here in the text notes (they are
mostly in the book). But the main idea:
Given L is in NP, what do we know?
L is decided by some NTM M. On an input of length n, any
computation of M runs in at most p(n) steps, where p(n) is a
polynomial. Without loss of generality, we may assume p(n) has
nonnegative integer coefficients (so it is easy to compute), and
p(n) >= n.
M accepts w iff there is some "history" of M accepting w. Such a
"history" just encodes one accepting computation path, it does not
need to mention other parts of the non-deterministic computation tree.
Given a particular input string w, we want to produce , so that w
is in L iff formula phi is satisfiable.
Idea: The variables of phi encode a table of symbols, big enough to
encode a history of M accepting w. We design phi so that it is
satisifiable iff there is a valid history of M accepting w.
Ok, the rest of the (long) argument is simply designing such a phi!
It has several parts. In particular, just by looking at the rules of
M, we can list all 2x3 "good" patterns of symbols that can occur in a
2x3 window of the table. (So, we can also list the "bad" patterns.)
Among other things, our phi will check that no 2x3 window has a
patten of symbols in the "bad" list.
The size of the table and of our final phi is O(p(n)^2), which is
polynomial. The big-Oh hides some big constants depending on M.
Assuming we get past the main argument, we can add this observation:
If we are careful, then the boolean formula phi is in
"conjunctive normal form". That is, an AND of clauses,
where a clause is an OR of literals, and a literal is
either a variable or a negated variable (or a constant).
So in fact, this restricted version of SAT is also NP-complete:
CNFSAT = { : phi is a satisifiable CNF boolean formula }