Proving NP-Completeness: Understanding NP-Hard Problems
Delve into the theory of NP-completeness to understand how problems are classified as NP-hard and NP-complete. Explore the definitions, concepts, and examples of NP-completeness, such as Independent Set and Satisfiability, to grasp the complexity of decision problems that fall within this class.
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
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 37: Proving NP-completeness
NP-Completeness Theory Definition. A problem is in P if it can be solved in polynomial time. Definition. A problem Q is in NP if Q is a decision problem and there is an algorithm AQ such that for any instance x of Q: 1. If x is a yes-instance, then there is a y such that AQ(x, y) = 1; 2. If x is a no-instance, then for all y, AQ(x, y) = 0; 3. AQ(x, y) runs in time polynomial in |x|. Definition. Let Q1 and Q2 be decision problems. We say that Q1 is poly-time reducible to Q2, written Q1 ? for any instance x1 of Q1, x1 is a yes for Q1 if and only if R(x1) is a yes for Q2. ? Q2, if there is a poly-time algorithm R such that ? Q. Definition. (1) A problem Q is NP hard if for every problem Q in NP, Q ? (2) A problem Q is NP complete if it is in NP and NP hard. Cook Theorem. SAT is NP complete. NP hard problems are hard. ? Q2, and Q1 is NP hard, then Q2 is NP hard. Lemma. If Q1 ? A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Example 1. Independent-Set is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn to make F = true? We show: ? IS SAT ? F = (?1 ?2 ?3 ?4 ?5) ( ?1 ?3 ?5) (?2 ?4 ?5) (?2 ?3 ?4 ?5) (?3 ?5) (?3 ?4 ?5)
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Example 1. Independent-Set is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn to make F = true? We show: ? IS SAT ? ?1 ?2 ?3 ?1 F = (?1 ?2 ?3 ?4 ?5) ( ?1 ?3 ?5) (?2 ?4 ?5) (?2 ?3 ?4 ?5) (?3 ?5) (?3 ?4 ?5) ?3 ?5 ?2 ?5 ?2 ?5 ?4 ?5 ?3 ?4 ?3 ?4 ?3 ?5 ?5 ?4
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Example 1. Independent-Set is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn to make F = true? We show: ? IS SAT ? ?1 ?2 ?3 ?1 F = (?1 ?2 ?3 ?4 ?5) ( ?1 ?3 ?5) (?2 ?4 ?5) (?2 ?3 ?4 ?5) (?3 ?5) (?3 ?4 ?5) ?3 ?5 ?2 ?5 ?2 ?5 ?4 ?5 ?3 ?4 ?3 ?4 ?3 ?5 ?5 ?4 (G, 6)
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Example 1. Independent-Set is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn to make F = true? We show: ? IS SAT ? ?1 ?2 ?3 ?1 F = (?1 ?2 ?3 ?4 ?5) ( ?1 ?3 ?5) (?2 ?4 ?5) (?2 ?3 ?4 ?5) (?3 ?5) (?3 ?4 ?5) ?3 ?5 ?2 ?5 ?2 ?5 ?4 ?5 ?3 ?4 ?3 ?4 ?3 F is a yes for SAT if and only if (G, 6) is a yes for IS ?5 ?5 ?4 (G, 6)
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C?
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? ? VC We show: IS ?
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? ? VC We show: IS ? Lemma. Let G be a graph of n vertices, then G has an independent set of k vertices if and only if G has a vertex cover of n-k vertices.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? ? VC We show: IS ? Lemma. Let G be a graph of n vertices, then G has an independent set of k vertices if and only if G has a vertex cover of n-k vertices. Proof. Let G = (V, E) and let I be a subset of vertices in G. Then, I is an independent set of G if and only if V I is a vertex cover of G.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? In I In V - I ? VC We show: IS ? Lemma. Let G be a graph of n vertices, then G has an independent set of k vertices if and only if G has a vertex cover of n-k vertices. Proof. Let G = (V, E) and let I be a subset of vertices in G. Then, I is an independent set of G if and only if V I is a vertex cover of G.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? In I In V - I ? VC We show: IS ? (G, n k) (G, k) Lemma. Let G be a graph of n vertices, then G has an independent set of k vertices if and only if G has a vertex cover of n-k vertices. Proof. Let G = (V, E) and let I be a subset of vertices in G. Then, I is an independent set of G if and only if V I is a vertex cover of G.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have two NP complete problems: SAT and IS. Example 2. Vertex-Cover is NP complete. Independent Set (IS). Given (G, k), where G is a graph and k is an integer, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? In I In V - I ? VC We show: IS ? (G, n k) (G, k) (G, k) is a yes for IS if and only if (G, n-k) is a yes for VC. Lemma. Let G be a graph of n vertices, then G has an independent set of k vertices if and only if G has a vertex cover of n-k vertices. Proof. Let G = (V, E) and let I be a subset of vertices in G. Then, I is an independent set of G if and only if V I is a vertex cover of G.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC.
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ?
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ? We show: Subset-Sum ? VC ?
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ? bij = 1 if vi is an end of ej, otherwise 0 We show: Subset-Sum ? ? VC ? ? e1 e2 . em b11 b21 b12 b22 . b1m b2m v1 (G, k) . v2 bij bn1 bn2 . bnm vn
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ? bij = 1 if vi is an end of ej, otherwise 0 We show: Subset-Sum ? VC ? e1 e2 . em b11 b21 b12 b22 . b1m b2m 1 v1 (G, k) . 1 v2 bij bn1 bn2 . bnm vn 1
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ? Regard each as an integer We show: Subset-Sum ? VC ? e1 e2 . em b11 b21 b12 b22 . b1m b2m 1 v1 (G, k) . 1 v2 bn1 bn2 . bnm vn 1
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ? Regard each as an integer We show: Subset-Sum ? VC ? e1 e2 . em b11 b21 b12 b22 . b1m b2m 1 v1 (G, k) . 1 v2 + There is a vertex cover of k vertices if and only if there are k rows whose sum is bn1 bn2 . bnm vn 1 k 1 1 . 1
NP-Completeness Theory A general procedure to prove NP hardness of a problem Q2: (1) Start with a known NP hard problem Q1; (2) Show Q1 ? ? Q2. Now we have three NP complete problems: SAT, IS, and VC. Example 3. Subset-Sum is NP complete. Vertex-Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Subset-Sum. Given a set S = {a1, a2, , an} of integers and an integer H, is there a subset S of S whose sum is exactly H, i.e., ?? ? ?? = H ? Regard each as an integer We show: Subset-Sum ? VC ? e1 e2 . em a1 b11 b21 b12 b22 . b1m b2m 1 v1 (G, k) . a2 1 v2 There is a vertex cover of k vertices if and only if there are k numbers in {a1, a2, , an} whose sum is bn1 bn2 . bnm vn an 1 k 1 1 . 1 But this is not a regular number
