NP-Completeness Theory and Computational Difficulties

CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 34: P and NP

NP-Completeness Theory A theory for realizing computational difficulties, i.e., infeasibility, of problems (in particular, those encountered in practice.)

NP-Completeness Theory A theory for realizing computational difficulties, i.e., infeasibility, of problems (in particular, those encountered in practice.) If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Examples. All problems we have studied in this class are in P. Sorting: O(n log n) = O(n2) Longest Common Subsequence: O(n2) Many graph problems solvable based on DFS and BFS: O(m+n) = O(L) Single Source Shortest Path: Dijktra: O(n2) or O(m log n) = O(n3), Bellman-Ford: O(nm) = O(n3) All-Pairs Shortest Path: Floyd-Warshall: O(n3), Johnson: O(nm log n) = O(n4) Minimum Spanning Tree: O(n2) or O(m log n) = O(n3), Bipartite Graph Matching: O(nm) = O(n3),

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Consider the following problems: 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? Independent Set (IS). Given a graph G and an integer k, 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 such that F = true? Partition. Given a set S = {a1, a2, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? These problems have wide applications in practice, but no one knows how to solve any of them efficiently (i.e., are they in P ?)

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? Independent Set (IS). Given a graph G and an integer k, 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, , xn), is there an assignment to x1, , xn such that F = true? Partition. Given a set S = {a1, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? NP-Completeness Theory

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? Independent Set (IS). Given a graph G and an integer k, 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, , xn), is there an assignment to x1, , xn such that F = true? Partition. Given a set S = {a1, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? NP-Completeness Theory These are the problems whose instances require a yes/no answer. This kind of problems are called decision problems. In general, they ask for the existence of solutions satisfying certain given conditions.

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? Independent Set (IS). Given a graph G and an integer k, 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, , xn), is there an assignment to x1, , xn such that F = true? Partition. Given a set S = {a1, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? NP-Completeness Theory These are the problems whose instances require a yes/no answer. This kind of problems are called decision problems. In general, they ask for the existence of solutions satisfying certain given conditions. Although it is not clear how we can find the desired solutions, it is easy to verify if anything given is a desired solution.

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? Independent Set (IS). Given a graph G and an integer k, 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, , xn), is there an assignment to x1, , xn such that F = true? Partition. Given a set S = {a1, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? NP-Completeness Theory These are the problems whose instances require a yes/no answer. This kind of problems are called decision problems. In general, they ask for the existence of solutions satisfying certain given conditions. Although it is not clear how we can find the desired solutions, it is easy to verify if anything given is a desired solution. This kind of problems are called NP-problems. Formally,

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? Independent Set (IS). Given a graph G and an integer k, 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, , xn), is there an assignment to x1, , xn such that F = true? Partition. Given a set S = {a1, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? NP-Completeness Theory These are the problems whose instances require a yes/no answer. This kind of problems are called decision problems. In general, they ask for the existence of solutions satisfying certain given conditions. Although it is not clear how we can find the desired solutions, it is easy to verify if anything given is a desired solution. This kind of problems are called NP-problems. Formally, 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|.

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? Independent Set (IS). Given a graph G and an integer k, 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, , xn), is there an assignment to x1, , xn such that F = true? Partition. Given a set S = {a1, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? NP-Completeness Theory These are the problems whose instances require a yes/no answer. This kind of problems are called decision problems. In general, they ask for the existence of solutions satisfying certain given conditions. Although it is not clear how we can find the desired solutions, it is easy to verify if anything given is a desired solution. This kind of problems are called NP-problems. Formally, 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|. Vertex-Cover, Independent-Set, Satisfiability, and Partition are all in NP.

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|.

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|. Example: The following Satisfiability (SAT) problem is in NP : Given a CNF formula F = F(x1, , xn), is there an assignment to x1, , xn to make F = true?

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|. Example: The following Satisfiability (SAT) problem is in NP : Given a CNF formula F = F(x1, , xn), is there an assignment to x1, , xn to make F = true? Algorithm ASAT(F, y) 1. if (F is not a CNF formula) return (0); 2. \\ so F is a CNF formula F(x1, , xn) if (y is not a binary string of n bits) return (0); 3. \\ so y = y1y2 yn return (F(y1, , yn)).

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|. Discussions. 1. In general, decision problems and their corresponding optimization problems have similar complexity, i.e., either both solvable in poly- time or both not. Thus, we will focus on decision problems.

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|. Discussions. 1. In general, decision problems and their corresponding optimization problems have similar complexity, i.e., either both solvable in poly- time or both not. Thus, we will focus on decision problems. Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Max Independent Set (MaxIS). Given a graph G, construct a largest independent set.

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|. Discussions. 1. In general, decision problems and their corresponding optimization problems have similar complexity, i.e., either both solvable in poly- time or both not. Thus, we will focus on decision problems. If MaxIS is solvable in time O(nc), then so is IS. Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Max Independent Set (MaxIS). Given a graph G, construct a largest independent set.

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|. Discussions. 1. In general, decision problems and their corresponding optimization problems have similar complexity, i.e., either both solvable in poly- time or both not. Thus, we will focus on decision problems. If MaxIS is solvable in time O(nc), then so is IS. Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Max Independent Set (MaxIS). Given a graph G, construct a largest independent set. If IS is solvable in time O(nc), then we have an algorithm max-size(G) that finds the size of max IS in time O(nc+1).

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|. Discussions. 1. In general, decision problems and their corresponding optimization problems have similar complexity, i.e., either both solvable in poly- time or both not. Thus, we will focus on decision problems. Time = O(nc+3) If MaxIS is solvable in time O(nc), then so is IS. Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Max Independent Set (MaxIS). Given a graph G, construct a largest independent set. MaxIS(G) 1. let k = max-size(G); 2. I = ; 3. for (h = k; h > 0; h--) find a vertex v such that max-size(G-N(v)) = h-1; I = I + v; G = G N(v); 4. return(I). If IS is solvable in time O(nc), then we have an algorithm max-size(G) that finds the size of max IS in time O(nc+1).