NP-Hard Problems in Computer Science
Explore the concept of NP-Hard problems, NP-Complete problems, reductions, and the implications of NP complexity classes in computational theory. Learn about the Cook-Levin Theorem and delve into challenging problems beyond NP complexity.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Outline NP, NP-hard, NP-complete Cook-Levin Theorem, first NP-hard problems Reductions INDEPENDENT SET to CLIQUE 3-SAT to INDEPENDENT SET
Polynomial time reductions A(X) { } Recall: General Reduction do something call B do something else Polynomial time reduction A(X) { } spend polynomial time to prepare an input Y for problem B return B(Y) Can only spend polynomial time Cannot do any post-processing.
Polynomial time reductions Reduce A to B: if there is a polynomial time algorithm that can transform an instance X of problem A to an instance Y of problem B in polynomial time, such that the answers are the same, then this is called a polynomial time reduction. X: instance of A Y: instance of B reduction If answer to X is YES, answer to Y is also YES If answer to X is NO, answer to Y is also NO A is easier, if B can be solved in polynomial time, then A can also be solved in polynomial time.
Hard problems: NP complete Hardest problems in NP. If A is in NP, and B is a NP complete problem, then A can be reduced to B. Corollary: If any of the NP complete problems can be solved in polynomial time, then P = NP. Theorem: Cook-Levin: Circuit-SAT is NP-complete.
Harder problems? There are problems that are not in NP. Example 1: Halting Problem: given the code of a program, check if it will terminate or not. This problem is not even solvable. Example 2: Playing chess: given a chess board with n*n size, with 4n chess pieces, decide whether the first player can always win. This is believed to be PSPACE complete, and very unlikely to be in NP.
NP-hard problems A problem A is NP-hard, if for all problem B in NP, B can be reduced to A in polynomial time. A is harder than all problems in NP, hence NP-hard. A problem A is NP-complete, if it is in NP and also NP-hard. NP-hard but not NP-complete? May not be a decision problem, e.g. longest path. May be even harder than NP-complete problems.
Relationships NP NP-hard NP-complete P
NP-complete problems Claim: All NP-complete problems are equally hard. For any two NP-complete problems A, B, A can be reduced to B and B can be reduced to A. Claim: If any NP-complete problem has a polynomial time algorithm, then P = NP. Claim: If A can be reduced to B, B can be reduced to C, then A can be reduced to C. How do we prove a problem is NP-complete?
Outline NP, NP-hard, NP-complete Cook-Levin Theorem, first NP-hard problems Reductions INDEPENDENT SET to CLIQUE 3-SAT to INDEPENDENT SET
The first NP-complete problem Gates Circuits
CIRCUIT-SAT problem Given a circuit with n inputs and 1 output, is there a possible input (represented by n-bit binary string) that makes the output 1? Clearly in NP: Prover gives the input as an n-bit string, Verifier follows the circuit and computes the output, check that it is indeed 1. Theorem[Cook-Levin] CIRCUIT-SAT is NP-complete.
Proof idea of Cook-Levin Verify(color[]) //color[] is an array with 0,1,2 FOR each edge (u,v) IF color[u]<>color[v] THEN RETURN FALSE RETURN TRUE NP-hard problem Verifier
Proof idea of Cook-Levin Verify(color[]) //color[] is an array with 0,1,2 FOR each edge (u,v) IF color[u]<>color[v] THEN RETURN FALSE RETURN TRUE 01010101010101 00101010101010 1010101011 Compiler Machine code Input: binary encoding of color[] Output: True/False CIRCUIT-SAT instance!
Outline NP, NP-hard, NP-complete Cook-Levin Theorem, first NP-hard problems Reductions INDEPENDENT SET to CLIQUE 3-SAT to INDEPENDENT SET
Other NP-hard Problems Reduction A B NP-Hard NP-Hard A is NP-hard For any problem C in NP, C is easier than A. A can be reduced to B A is easier than B For any problem C in NP, C is easier than B B is NP-hard
General Recipe for reductions In order to prove B is NP-hard, given that we know A is NP hard. Reduce A to B. What is a complete reduction? 1. Given an instance X of A, construct an instance Y of B. 2. 3. Prove that if answer to X is YES, answer to Y is also YES. Prove that if answer to X is NO, answer to Y is also NO. (Usually: prove the contrapositive: if answer to Y is YES, answer to X is also YES)
INDEPENDENT SET Given a graph, decide whether there is a set of k vertices, such that no two vertices in the set are connected by an edge.
CLIQUE Given a graph, decide whether there is a set of k vertices, such that all pairs of vertices in the set are connected by an edge. Claim: INDEPENDENT SET can be reduced to CLIQUE.
Reduction from INDEPENDENT SET to CLIQUE Step 1: Given an instance X of INDEPENDENT SET, construct an instance Y of CLIQUE. Idea: Find similarities/differences of the problems. INDEP. SET: find vertices such that they are not connected. CLIQUE: find vertices such that they are connected.
3-SAT Literals: A variable (?1), or the negation of a variable (?1). Clause: Logic OR of literals (?1 ?3 ?5) Conjunctive Normal Form: and of or s. ?1 ?3 ?5 ?2 ?3 ?4 ?1 ?4 ?5 3-SAT: Given a conjunctive normal form, where each clause contains at most 3 literals, decide whether there is a value of variables such that the formula is satisfied (A clause is satisfied if one of its literals is true; The formula is satisfied if ALL clauses are satisfied.)
Reductions Claim: CIRCUIT-SAT can be reduced to 3-SAT. (therefore 3-SAT is also NP-complete). Claim: 3-SAT can be reduced to INDEPENDENT SET. IND- SET CIRCUIT -SAT 3-SAT CLIQUE NP-complete NP-complete NP-complete NP-complete
Reduction from 3-SAT to INDEPENDENT SET Step 1: Given an instance X of 3-SAT, construct an instance Y of INDEPENDENT SET. Problem: the two problems look totally different. Idea: Construct Gadgets : for each concept in 3- SAT (variables, clauses), construct a part of instance of INDEP. SET (some vertices/edges) so that we can connect the two problems.
Gadget for variables Variable xi: either true or false Gadget: A graph with two different independent sets, corresponding to xi = true or false. Many constructions, but easiest one ui vi Hope: ui in independent set xi = true vi in independent set xi = false
Gadget for Clauses Clause: (?1 ?3 ?5) Interpretation: x1 = true or x3 = true or x5 = false not all of v1, v3, u5 in independent set Idea: construct a gadget that connects to v1, v3, u5, such that when they are not all in independent set, we can put one vertex in gadget to indep. set; when they are all in indep. set, then we cannot put any vertex in gadget into indep set.
Gadget for Clauses Clause: (?1 ?3 ?5) Goal: When clause is not satisfied, cannot select any vertex in gadget. v1 When clause is satisfied, can select exactly one vertex in gadget v3 Gadget u5 This encourages all the clauses to be satisfied.
Gadget for Clauses Clause: (?1 ?3 ?5) Goal: When clause is not satisfied, cannot select any vertex in gadget. v1 w1 When clause is satisfied, can select exactly one vertex in gadget v3 w2 u5 w3 This encourages all the clauses to be satisfied.
