Understanding NP-Hard Problems and NP-Completeness
Delve into the complexities of NP-hard problems, NP-complete problems, and the relationships between NP, NP-hard, and NP-complete classes. Learn about easy-to-verify problems in NP, the concept of NP-completeness, the first NP-complete problem - Gates Circuits, and the NP-complete problem CIRCUIT-SAT. Uncover the significance of Cook-Levin Theorem and the proof idea behind it. Explore how to prove a problem is NP-complete and understand the implications of P vs. NP in computational complexity theory.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Easy to verify problems: NP All decision problems such that we can verify the correctness of a solution in polynomial time. Example: 3-COLORING input Prover: Yes, the graph can be colored by 3 colors.
Easy to verify problems: NP All decision problems such that we can verify the correctness of a solution in polynomial time. Example: 3-COLORING Prover: Yes, the graph can be colored by 3 colors. Verifier: OK, that is indeed a solution.
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?
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!
Other NP-hard Problems Reduction A B NP-Hard NP-Hard
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.
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
