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 }