Reductions and NP-Completeness

Understanding hardness through reductions

ReductionsPolynomial Time ReductionsNP-completeness can seem to be very abstract and not useful when designing algorithms. Why does it help to recognize that a certain problem can be “verified” quickly?Well, it turns out that many of the problems mentioned above are strictly different flavors of the same problem. That is, if you can solve one of the problems quickly (in polynomial time), you would be able to solve any other problem in this list quickly as well. Karp, in his seminal paper, found 21 such problems, but today, we know of hundreds of thousands of them. These problems are known as NP-complete problems.How was Karp able to prove that all these problems are effectively the same? This is what the idea of a reduction is. We say that some decision problem 𝐴 is polytime-reducible to 𝐵 (sometimes we use the notation 𝐴≤𝑝𝐵) if there is some algorithm 𝑓 which runs in polynomial time such that𝑥∈𝐴⟺𝑓(𝑥)∈𝐵Here’s what this intuitively says. Let’s say we had a magic black box that could tell us the yes/no value of if a problem is in 𝐵. Then, if there is a reduction 𝑓 which allows us to solve 𝐴 by using this black box for 𝐵, we can say that 𝐵 is strictly “harder” than 𝐴. Because, if we are ever able to solve 𝐵 with some algorithmic black-box, our reduction would immediately give us an algorithm for solving 𝐴.So here’s what Karp was able to prove. He took CLIQUE, and then showed how it could be solved via IS. Then he took IS, and showed how it could be solved via HP. Then he took HP, and showed how it could be solved via TSP. Finally, he took TSP, and showed how it could be solved with CLIQUE. In other words, Karp took his 21 problems and made a reduction chain something along the lines ofCLIQUE≤𝑝IS≤𝑝HP≤𝑝TSP≤𝑝CLIQUEthereby showingCLIQUE≡𝑝IS≡𝑝HP≡𝑝TSPwhich says that if we could solve any one of these problems, we could solve them all.Note, this works because reductions are transitive, A≤𝑝B and B≤𝑝C⟹A≤𝑝C, which is true because the reduction from A to B can be composed with the reduction from B to C to get a reduction from A to C.NP-completenessSeeing this, a natural question is “is there a hardest problem in P?”, or “is there a hardest problem in NP?”. With reductions, we can answer this. First, what does it mean to be the “hardest” problem?We say that a problem 𝐴 is “harder” than any problem in NP if𝐵≤𝑝𝐴for all 𝐵∈NP. Usually, we call the set of all such hard problems NP-hard, and so we would say that the 𝐴 above satisfies 𝐴∈NP-hard.However, not all of these “hard” problems are interesting. For example, one such problem 𝐴 could be the problem “always output the correct answer of a nondeterministic Turing machine” and it can clearly trivially solve all the problems in NP. However, this problem is definitely not in NP.So, to make this more interesting, we define a class of problems that are the hardest within NP. That is, they are both NP-hard, and they are in NP. These problems are called NP-complete.Cook-Levin TheoremTheorem: 3SAT is NP completeProof: First we need to show 3SAT∈NP. This is pretty simple — given some boolean formula, our witness can be an answer to the boolean formula, and our verifier can be an algorithm that plugs in that answer and checks if it evaluates to true or not.The second thing we need to show is that, 3SAT∈NP-hard. This, unfortunately, is pretty difficult. How do we show that every single problem in NP can be reduced to a polynomial sized instance of 3SAT? Thankfully, Cook and Levin were able to do it, with some inter­esting trick involving simulating Turing machines and their tapes. Their construction is pretty complicated though, so we will spare you the details here.Fortunately, thanks to Cook and Levin’s hard work, showing a problem is NP-hard is no longer as time-consuming and difficult! Now, since we know 3SAT is NP complete, if we want to show A is NP-complete it suffices to first show A∈NP, and then to find some reduction3SAT≤𝑝AThis is because 3SAT is harder than every problem, and A is harder than 3SAT, so A is harder than every problem!Below is the picture to keep in your head.It’s important to note that the picture above is what computer scientists generally agree is probably true. It’s still possible that we will be able to find some fast algorithm to solve an NP-complete or NP-hard problem, in which case, the three sets collapse to give P=NP=NP-complete.Let’s go take a slight detour to analyze a specific reduction between 3SAT and CLIQUE, and see what it allows us to say.Reduction of 3SAT to CliqueReduction: We want to convert instances of 3CNF formulas to instances of graphs in poly­nomial time. In the constructed graph, cliques of a specified size correspond to satisfying assignments of the 3CNF formula. So a solution for a 𝑘-clique problem can be directly used as a solution for the 3CNF problem.1.Let 𝜑=(𝑎1∨𝑏1∨𝑐1)∧(𝑎2∨𝑏2∨𝑐2)∧…∧(𝑎𝑘∨𝑏𝑘∨𝑐𝑘)2.Reduce this 3CNF into an undirected graph 𝐺 by grouping the vertices of 𝐺 into 𝑘 groups of 3 vertices, each called a triple3.Each triple corresponds to one of the clauses in 𝜑. Each vertex in a triple corresponds to a literal in the corresponding clause.4.Connect all vertices by an edge except (1) vertices in the same triple or (2) vertices representing complementary literals, e.g., 𝑥 and ¬𝑥.Example: Here’s an example on the boolean formulaΦ=(𝑥1∨¬𝑥2∨¬𝑥3)∧(¬𝑥1∨𝑥2∨𝑥3)∧(𝑥1∨𝑥2∨𝑥3)Notice that almost all the edges are included except those within a triplet, and those going between the negation of the same literal (like 𝑥1 and ¬𝑥1).Proof. Now that we have our reduction, we need to formally prove that it works! We do this by showing a 3CNF input Φ is satisfiable if and only if the resulting 𝐺 from the reduction has a 𝑘-clique.(1) Φ satisfiable ⟹ 𝐺 has 𝑘-clique. If Φ is satisfiable, then in the satisfying assignment, at least one literal in each clause is true. Each pair of those vertices must be connected, since we connect them all except complementary ones and ones within the same triple. Therefore 𝐺 contains a 𝑘-clique.(2) 𝐺 has 𝑘-clique ⟹ Φ satisfiable. We can prove this by the contrapositive. If Φ is not satisfiable, then for any assignment there must be at least one clause not satisfied. This means that any selection of literals includes a complementary pair. These are not connected in 𝐺, so 𝐺 does not have a 𝑘-clique.Alternatively, assume 𝐺 has a 𝑘-clique. It must include one vertex per clause/triple, and since no two can be complementary, we can set those literals true, creating a consistent truth assignment. Therefore, Φ is satisfiable.■What does this all mean?Ok, so we’ve successfully performed a reduction. Since 3SAT is NP-complete and we have3SAT≤𝑝CLIQUEwe also knowCLIQUE≤𝑝3SATso3SAT≡𝑝CLIQUEThat makes CLIQUE also NP-complete!Now recall our original chain:CLIQUE≡𝑝IS≡𝑝HP≡𝑝TSPAnd since 3SAT≡𝑝CLIQUE,3SAT≡𝑝CLIQUE≡𝑝IS≡𝑝HP≡𝑝TSPTherefore, all of these problems are NP-complete!This is how we’ve come up with so many NP-complete problems: we reduce from one known NP-complete problem to another. These chains form a web of reductions, like shown below.Why is this useful? Because NP-completeness gives us permission to give up! If you reduce your hard problem to a known NP-complete problem, you can (often justifiably) say no efficient algorithm likely exists — at least unless P = NP!Further Reading1.David Lu’s Notes2.P vs NP - Wikipedia