Techniques for Proving NP-Completeness2. Local Replacement3. Component DesignThe Art of Proving HardnessGuideline 1Guideline 2Guideline 3Guideline 4Guideline 5Guideline 63-Satisfiability3-SATReducing SAT to 3-SATContinuing the Reduction….Generalizations about SATInteger ProgrammingIs Integer Programming NP-Hard?We must show that:Things to NoticeMore Things to NoticeThe Independent Set ProblemReducing 3-SAT to Independent SetIncluding Clauses in the ReductionTying it all together...Hamiltonian CycleThe ReductionObservations….Joining ContraptionsSlide 29Tying the Chains TogetherBeginning a TransformThe Final TransformTechniques for ProvingNP-Completeness1. Restriction - Show that a special case of the problem you are interested in is NP-complete. For example:• The problem of finding a path of length k is a superset of the Hamiltonian Path problem. •The problem of finding a subgraph of size j where each vertex is at least degree k is an expanded version of the Clique problemIn general, all we need to do is prove part of a problem hard for the entire problem to be classified NP-hard.2. Local ReplacementMake local changes to the structure. An example is the SAT to SAT-3 reduction. Another example is showing isomorphism is no easier for bipartite graphs: For any graph, replacing an edge with makes it bipartite.3. Component DesignThese are the ugly, elaborate constructions, such as the ones we use to reduce SAT into vertex cover, and subsequently vertex cover into Hamiltonian Circuit.The Art of Proving HardnessProving that problems are hard is an skill. Once you get the hang of it, it becomes surprisingly straightforward and intuitive.Indeed, the dirty little secret of NP-completeness proofs is that they are usually easier to recreate than explain, in the same way that it is usually easier to rewrite old code than to try to understand it.Guideline 1Make your source problem as simple as possible.Never try to reduce the general Traveling Salesman Problem to prove hardness. Better, use Hamiltonian Cycle. Even better, don’t worry about closing the cycle, and use Hamiltonian Path.If you are aware of simpler NP-Complete problems, you should always use them instead of their more complex brethren. When reducing Hamiltonian Path, you could actually demand the graph to be directed, planar or even 3-regular if any of these make an easier reduction.Guideline 2Make your target problem as hard as possible.Don’t be afraid to add extra constraints or freedoms in order to make your problem more general.Perhaps you are trying to prove a problem NP-Complete on an undirected graph. If you can prove it using a directed graph, do so, and then come back and try to simplify the target, modifying your proof. Once you have one working proof, it is often (but not always) much easier to produce a related one.Guideline 3Select the right source problem for the right reason.3-SAT: The old reliable. When none of the other problems seem to work, this is the one to come back to.Integer Partition: This is the one and only choice for problems whose hardness requires using large numbers.Vertex Cover: This is the answer for any graph problems whose hardness depends upon selection.Hamiltonian Path: This is the proper choice for most problems whose answer depends upon ordering.Guideline 4Amplify the penalties for making the undesired selection.If you want to remove certain possibilities from being considered, it may always be possible to assign extreme values to them, such as zero or infinity.For example, we can show that the Traveling Salesman Problem is still hard on a complete graph by assigning a weight of infinity to those edges that we don’t want used.Guideline 5Think strategically at a high level, and then build gadgets to enforce tactics.You should be asking yourself the following types of questions: “How can I force that either A or B, but not both are chosen?” “How can I force that A is taken before B?” “How can I clean up the things that I did not select?”After you have an idea of what you want your gadgets to do, you can start to worry about how to craft them. The reduction to Hamiltonian Path is a perfect example.Guideline 6When you get stuck, alternate between looking for an algorithm or a reduction.Sometimes the reason you cannot prove hardness is that there exists an efficient algorithm that will solve your problem! Techniques such as dynamic programming or reducing to polynomial time graph problems sometimes yield surprising polynomial time algorithms. Whenever you can’t prove hardness, it likely pays to alter your opinion occasionally to keep yourself honest.3-SatisfiabilityInstance: A collection of clause C where each clause contains exactly 3 literals, boolean variable v. Question: Is there a truth assignment to v so that each clause is satisfied? Note: This is a more restricted problem than normal SAT. If 3-SAT is NP-complete, it implies that SAT is NP-complete but not visa-versa, perhaps longer clauses are what makes SAT difficult?1-SAT is trivial.2-SAT is in P (you will prove this in your last homework)3-SATTheorem: 3-SAT is NP-Complete Proof:1) 3-SAT is NP. Given an assignment, we can just check that each clause is covered.2) 3-SAT is hard. To prove this, a reduction from SAT to 3-SAT must be provided. We will transform each clause independently based on its length.Reducing SAT to 3-SATSuppose a clause contains k literals:if k = 1 (meaning Ci = {z1} ), we can add in two new variables v1 and v2, and transform this into 4 clauses:{v1, v2, z1} {v1, v2, z1} {v1, v2, z1} {v1, v2, z1}if k = 2 ( Ci = {z1, z2} ), we can add in one variable v1 and 2 new clauses: {v1, z1, z2} {v1, z1, z2}if k = 3 ( Ci = {z1, z2, z3} ), we move this clause as-is.Continuing the Reduction….if k > 3 ( Ci = {z1, z2, …, zk} ) we can add in k - 3 new variables (v1, …, vk-3) and k - 2 clauses: {z1, z2, v1} {v1, z3, v2} {v2, z4, v3} … {vk-3, zk-1, zk}Thus, in the worst case, n clauses will be turned into n2 clauses. This cannot move us from polynomial to exponential time.If a problem could be solved in O(nk) time, squaring the number of inputs would make it take O(n2k) time.Generalizations about SATSince any SAT solution will satisfy the 3-SAT instance and a 3-SAT solution can set variables giving a SAT solution, the problems are equivalent. If there were n clauses and m distinct literals in the SAT instance, this transform takes O(nm) time,