Last lectues: CNF <= IS = VC <= Set cover = means reduction in both directions. Today: Circuit Sat CNF <= CS SC <= CS CS <= CNF Working definitions of classes NP, NP-hard, NP-complete The class P P subseteq NP Central question is P = NP? ----- Circuit Sat: Input: a combinational circuit made out of and, or, not gates. Circuit can have many inputs, one output. Output: Is there a way to assign input values such that circuit output evaluates to true? Problem size: total number of inputs, summed over all gates. ---------------------- CNF <= CS Key observation: Formula = Circuit formula variables = circuit inputs Negated literals : obtain using a not gate from corresponding input Clause : OR gate applied to of corresponding literals Product : AND of outputs of OR gate. Clearly, formula value = circuit output. ----- Important key idea: Class of CNF instances <= Class of CS instances. CNF is a special case of CS. So clearly CS cannot be easier. -------- SC Input: collection S of sets s1,...,sn, k Output: Does there exist a subcollectin of k sets whose union is the union of the S "Does a subcollection cover S" Bipartite graph representation: LHS elements, RHS sets. ------ SC <= CS Need F(S,k){ circuit which is satisfiable iff S' exists} F must run in polytime. ------- Correspondence: SC : Does there exist S' CS : Does there exist an input assignment SC : S' covers all elements CS : Circuit evaluates to true Key idea: All possible input assignments = All possible choices of S' Circuit mimics the conditions required of S' ---- Circuit construction n = |S|. Circuit will have n inputs: x1..xn. Each input assignment is a 0-1 vector, and so corresponds to subset of S. For every element t: Let t1...tk denote the sets in S that contain it. So we put in a gate t connecting these inputs together. t has output true iff at least one of the sets containing t is included. Attach all such gate outputs to an and gate X. And gate output is true if some set is selected to cover every element. Construct a counting circuit : which returns true if the number of 1s is exactly k. Let Y = output of counting circuit Circuit output = X and Y. ---- Circuit has size polynomial in the size of the graph. Suppose SC instance has output true. Say S' is the required subcollection. Let s'1,..s'k be the sets in S'. Construct an input assignment in which the bits corresponding to s'i are 1, rest 0. Will Y be true: yes, exactly k bits are 1. Will X be true: true only if each t gate gives output true. Each t gate gives output true if one of the inputs is true = one of the sets containing t is selected. But we know S' contains such a set. Hence t is true. So circuit will also output t. Suppose SC has solution false, i.e. no S' exists. We need to prove that circuit has no satisfying assignment. We prove the contrapositive: If circuit has a satisfying assignment, then S' exists. Take the satisfying assignment, if x_i=1 in it, include s_i in S'. Since the assignment is satisfying, both X and Y must be true. So exactly k x_is must be true, so S' will contain exactly k sets. Since X is true, all the t gates output true. but then one of the inputs to that must be true, i.e. one of the s_i containing t must be selected, for every t. Hence S' does cover every element. Finally, the circuit (some convenient representation) can ge generated from G,k in polytime. ----------- Important point to note: Our circuit does not solve the SC instance. It only mirrors the constraints of the SC instance. Devising a circuit which solves the SC instance is much more work. If we could do it in polytime, it we would have a polynomial time algorithm for SC which we no one has found so far. We are simply translating questions from the SC language to the CS language without answering them. Does God exist : Ishwar ka astitwa hai? You dont need to answer the question in order to translate it. This reduction is based on a general principle. Suppose problem P asks whether a certain combinatorial object O satisfying certain constraints C exists. Then to reduce P to CS, the instance map F just needs to do the following: Construct a circuit that takes as input a representation of any candidate object, and the circuit elements check whether the object satisfies the constraints C, and output true if it does. Make sure you understand this theme in the reduction of SC to CS. ----------- Thm Circuit-Sat <= CNF Sat Proof: Idea 1: write down the formula for the circuit -- convert it to a cnf formula. Doesnt work: converting to cnf can increase the size of the formula exponentially. Example: convert the formula ab + cd +ef to CNF. Answer: (a+c+e)(...) In general if there are k terms in the DNF and each term has l literals, the CNF will have l^k clauses. Our translation function F will not work in polytime. Clever idea: We will write down a short formula which represents the statement: "There is a way to set the inputs to the circuits and the values in the internal wires consistently with the functioning of the gates and such that the output is T." This statement will be represented in CNF. If the statement is true then clearly the circuit has a satisfying assignment. If the circuit has a satisfying assignment, then clearly the statement is true. Note that the formula has more variables than the circuit. Solution: F(Circuit description){Construct a CNF formula as follows. 0. Assume that all gates in the circuit are at most 2 input. If not replace each k input gate by k-1 2 input gates in series. 1. Variables in the formula: one per wire in the given circuit. Wire = inputs/outputs of all gates. 2. For each and gate i with inputs a_i,b_i, output c_i: write down a formula which represents that c_i has the correct value given the values of a_i,b_i. (ab <-> c) convert this to cnf. = (ab -> c) (c -> ab) = (c + (ab)') (ab + c') = (c + a' + b') (a + c')(b + c') Call this collection G_i. Do the same for AND gates and NOT gates. Since the gate has at most 3 wires, the cnf clauses will have at most 3 variables. The number or cnf clauses can at most be 8. 3. f1 = conjunction of all G_i above and x_o where x_o is the variable associated with the output. return resulting formula } Correctness: If circuit is satisfiable formula is: consider the input values in the satisfying assignment. Compute the values on each wire arising out of these input values. Feed these values into the formula. Put in arbitrary values for the extra variables. For each gate The values of the inputs and outputs must satisfy the clauses. The output clause will also be satisfied since o is true. The formula has a satisfying assignment If circuit is not satisfiable then formula is not. If formula is satisfiable then circuit is also. Consider the satisfying assignment for the formula. Pick up the values corresponding to the input wires. Put those on the formula inputs. When the circuit operates, the values on the wires will be exactly as given in the fomula. Also the output wire will be 1. polytime: for each gate we have to emit at most 8 clauses. Each clause can become 4 clauses in step 4. total size/time clearly polynomial. ------------------------------------------ 3CNF : CNF formulae in which every clause has exactly 3 literals. 3CNF instances are clearly subset of CNF instances, and hence 3 CNF is a special case. So 3CNF <= CNF. The reverse direction holds, more indirectly. First we prove: CS <= 3 CNF Proof: as above except for a minor modification. 4. All clauses in f1 have at most 3 literals. To convert a 2-clause (a+b) to a 3-clause, just construct a new variable x and use (a+b+x)(a+b+x'). Note that (a+b) is identical to this and is thus satisfied iff (a+b+x)(a+b+x') is satisfied. In this way you can increase the length of any clause to 3. The rest of the proof works with little modification -- we can set x however we want, it does not matter. Now that we have CNF <= CS, together we have CNF <= 3 CNF. --------- What we have done so far: 3 CNF SAT <= CNF SAT <= IS <= VC <= IS <= Circuit Sat <= 3 CNF SAT Some unofficial definitions. NP (noun) : class of problems that can be reduced to Circuit Sat. "No harder than CS" NP-hard (adjective) : Problems that Circuit Sat can be reduced to. Also described as "problems reduced FROM circuit sat". "No easier than CS" NP-COMPLETE (adjective): Problems that are NP-hard and in NP. "Equivalent to CS" All NP-complete prolems are equivalent as far as designing polytime algorithms. Either there exist polytime algorithms for all or there do not exist for even one. CS community belief: NP-completeness problems do not have polytime algorithms. Take-home message: Before you spend too much time on designing an algorithm for some problem X, check using reductions, if it is NP-hard. In which case work further only if you feel you have an idea that so many clever computer scientists did not have. How do you see if X is likely to be hard? See if you can reduce to X from CS. Reduction from CS can be done directly, or we can reduce from any other problem Y such that CS <=P Y. ----- Class P : (decision) problems that can be solved in polynomial time. P <= CS F(instance q of a problem Q in P){ y = solution to q If q = T, return any circuit that has a satisfying assignment, say a circuit computing (A+B). Else return any circuit without a satisfying assignment, say circuit computing AA', where A' = complement of A. } We are doing something here that we have said all along is wrong: solving the instance q. This works because q can actually be solved in polynomial time. For problems Q which polynomial time algorithms are not known, solving the instance cannot happen in polytime -- but our reduction needs to happen in polytime. --------- The central question in computer science is: "Is P = NP?" We have shown that P is contained in NP. But does NP contain problems not in P, i.e. which cannot be solved in polytime? In other words can CS, IS, SC, and so on be solved in polytime? We dont know the answer. Later we will see the official definition of these classes, which will reveal more interesting aspects of the question.