CS 577 – Computational Intractability
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
CInotmrapuctabtilintyal
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Computational Intractability
Easy Problems
Problems that can be solved by efficient algorithms. Polynomial running time.
Complexity class: P
1/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Computational Intractability
Easy Problems
Problems that can be solved by efficient algorithms. Polynomial running time.
Complexity class: P
Hard Problems
Problems for which we do not know how to solve efficiently.
1/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Computational Intractability
Easy Problems
Problems that can be solved by efficient algorithms. Polynomial running time.
Complexity class: P
Hard Problems
Problems for which we do not know how to solve efficiently.
NP-hard
1/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Computational Intractability
Easy Problems
Problems that can be solved by efficient algorithms. Polynomial running time.
Complexity class: P
Hard Problems
Problems for which we do not know how to solve efficiently.
NP-hard
NP-complete
1/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Decision Problem
Optimization:
Bipartite Matching
Given a bipartite graph G, find the largest matching.
2/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Decision Problem
Optimization:
Bipartite Matching
Given a bipartite graph G,
find the largest matching.
Decision:
Bipartite Matching
Given a bipartite graph G, is
there a matching of size ≥ k?
Decision Problem
binary output: yes / no answer.
2/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Decision Problem
Optimization:
Bipartite Matching
Given a bipartite graph G,
find the largest matching.
⇐⇒
Decision:
Bipartite Matching
Given a bipartite graph G, is
there a matching of size ≥ k?
Optimization to Decision
Solve the optimization version.
If the solution of size ≥ k, return yes.
2/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Decision Problem
Optimization:
Bipartite Matching
Given a bipartite graph G,
find the largest matching.
⇐⇒
Decision:
Bipartite Matching
Given a bipartite graph G, is
there a matching of size ≥ k?
Decision to Optimization
Upper bound on maximum matching is N = min(|A|, |B|). For k = N to 0, return first k that returns yes.
2/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Decision Problem
Optimization:
Bipartite Matching
Given a bipartite graph G,
find the largest matching.
⇐⇒
Decision:
Bipartite Matching
Given a bipartite graph G, is
there a matching of size ≥ k?
Decision to Optimization
Upper bound on maximum matching is N = min(|A|, |B|). For k = N to 0, return first k that returns yes.
(Or, binary search between [0, N].)
2/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Reductions
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Polynomial-Time Reduction
Problem Reduction: Y ≤p X
Consider any instance of problem Y.
Assume we have a black-box solver for problem X.
3/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Polynomial-Time Reduction
Problem Reduction: Y ≤p X
Consider any instance of problem Y.
Assume we have a black-box solver for problem X.
Efficiently transform an instance of problem into a polynomial number of instances of X that we solve
(black-box solver) for problem X and aggregate efficiently to solve Y.
3/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Polynomial-Time Reduction
Problem Reduction: Y ≤p X
Consider any instance of problem Y.
Assume we have a black-box solver for problem X.
Efficiently transform an instance of problem into a polynomial number of instances of X that we solve
(black-box solver) for problem X and aggregate efficiently to solve Y.
Y is polynomial-time reducible to X
Suppose Y ≤p X. If X is solvable in polynomial time, then Y can be solved in polynomial time.
3/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Polynomial-Time Reduction
Problem Reduction: Y ≤p X
Consider any instance of problem Y.
Assume we have a black-box solver for problem X.
Efficiently transform an instance of problem into a polynomial number of instances of X that we solve
(black-box solver) for problem X and aggregate efficiently to solve Y.
Y is polynomial-time reducible to X
Suppose Y ≤p X. If X is solvable in polynomial time, then Y can be solved in polynomial time.
X is at least as hard as Y
Suppose Y ≤p X. If Y cannot be solved in polynomial time, then
X cannot be solved in polynomial time.
3/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Independent Set ⇐⇒ Vertex Cover
Given a graph G and a number k.
Independent Set (IS)
Does G contain an IS of
size ≥ k?
S ⊆ V is independent if
no 2 nodes in S are adjacent.
Vertex Cover (VC)
Does G contain a vertex
cover of size ≤ k?
S ⊆ V is vertex cover if
4/40
every edge is incident to at least 1 node in S.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Independent Set ⇐⇒ Vertex Cover
Given a graph G and a number k.
Independent Set (IS)
Does G contain an IS of
size ≥ k?
S ⊆ V is independent if
no 2 nodes in S are adjacent.
Vertex Cover (VC)
Does G contain a vertex
cover of size ≤ k?
S ⊆ V is vertex cover if
4/40
every edge is incident to at least 1 node in S.
TopHat 1: What is size of the largest independent set?
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Independent Set ⇐⇒ Vertex Cover
Given a graph G and a number k.
Independent Set (IS)
Does G contain an IS of
size ≥ k?
S ⊆ V is independent if
no 2 nodes in S are adjacent.
Vertex Cover (VC)
Does G contain a vertex
cover of size ≤ k?
S ⊆ V is vertex cover if
the smallest vertex cover?
4/40
every edge is incident to at least 1 node in S.
TopHat 2: What is size of
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Independent Set ⇐⇒ Vertex Cover
Given a graph G and a number k.
Independent Set (IS)
Does G contain an IS of
size ≥ k?
S ⊆ V is independent if
no 2 nodes in S are adjacent.
Vertex Cover (VC)
Does G contain a vertex
cover of size ≤ k?
S ⊆ V is vertex cover if
4/40
every edge is incident to at least 1 node in S.
Theorem 1
Let G = (V, E) be a graph. Then S is an independent set if and only if its complement V \ S is a vertex cover.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Independent Set ⇐⇒ Vertex Cover
Given a graph G and a number k.
Independent Set (IS)
Does G contain an IS of
size ≥ k?
S ⊆ V is independent if
no 2 nodes in S are adjacent.
Vertex Cover (VC)
Does G contain a vertex
cover of size ≤ k?
S ⊆ V is vertex cover if
every edge is incident to at least 1 node in S.
Theorem 1
Let G = (V, E) be a graph. Then S is an independent set if and only if its complement V \ S is a vertex cover.
Proof.
⇒: Suppose S is an IS. For any edge (u, v), at most one of
{u, v} ∈ S. Hence, one of {u, v} ∈ V \ S.
4/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Independent Set ⇐⇒ Vertex Cover
Given a graph G and a number k.
Independent Set (IS)
Does G contain an IS of
size ≥ k?
S ⊆ V is independent if
no 2 nodes in S are adjacent.
Vertex Cover (VC)
Does G contain a vertex
cover of size ≤ k?
S ⊆ V is vertex cover if
every edge is incident to at least 1 node in S.
Theorem 1
Let G = (V, E) be a graph. Then S is an independent set if and only if its complement V \ S is a vertex cover.
Proof.
⇐: Suppose V \ S is a VC. Any edge (u, v) with both ∈ S would contradict that V \ S is a VC.
4/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Packing and Covering Problems
Packing Problem
Independent Set
Goal is to pack as many vertices as possible without violating edge constraints.
Covering Problem
Vertex Cover
Goal is to cover all the edges in the graph using as few vertices as possible.
5/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Set Cover (SC)
Problem Definition A universe U of n elements.
A collection of subsets of
U: S1, S2, . . . , Sm.
A number k.
Goal: Does there exist a collection of at most k of the subsets whose unions equal U.
6/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Vertex Cover (VC) to Set Cover (SC)
Theorem 2
VC ≤p SC
7/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Vertex Cover (VC) to Set Cover (SC)
Theorem 2
VC ≤p SC
Proof.
TH3: For the proof, do we assume a VC or a SC black-box?
7/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Vertex Cover (VC) to Set Cover (SC)
Theorem 2
VC ≤p SC
Proof.
Assume that we have a black-box solver for SC.
7/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Vertex Cover (VC) to Set Cover (SC)
Theorem 2
VC ≤p SC
Proof.
For each vertex v ∈ V:
Assume that we have a black-box solver for SC. Consider an arbitrary instance of VC on G = (V, E).
Set U = E.
Create a set consisting of each edge incident to v.
7/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Vertex Cover (VC) to Set Cover (SC)
Theorem 2
VC ≤p SC
Proof.
For each vertex v ∈ V:
Assume that we have a black-box solver for SC. Consider an arbitrary instance of VC on G = (V, E).
Set U = E.
Create a set consisting of each edge incident to v.
Direct correspondence between VC and SC.
VC ≤ k ⇐⇒ SC ≤ k
7/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Set Packing (SP)
Problem Definition A universe U of n elements.
A collection of subsets of
U: S1, S2, . . . , Sm.
A number k.
Goal: Does there exist a collection of at least k of the subsets that don’t intersect.
8/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Set Packing (SP)
Problem Definition A universe U of n elements.
A collection of subsets of
U: S1, S2, . . . , Sm.
A number k.
Goal: Does there exist a collection of at least k of the subsets that don’t intersect.
Exercise: Show that IS ≤p SP
8/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Independent Set (IS) to Set Packing (SP)
Theorem 3
IS ≤p SP
9/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Independent Set (IS) to Set Packing (SP)
Theorem 3
IS ≤p SP
Proof.
Assume that we have a black-box solver for SP.
9/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Independent Set (IS) to Set Packing (SP)
Theorem 3
IS ≤p SP
Proof.
For each vertex v ∈ V:
Assume that we have a black-box solver for SP. Consider an arbitrary instance of IS on G = (V, E).
Set U = E.
Create a set consisting of each edge incident to v.
9/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Reduction: Independent Set (IS) to Set Packing (SP)
Theorem 3
IS ≤p SP
Proof.
For each vertex v ∈ V:
Assume that we have a black-box solver for SP. Consider an arbitrary instance of IS on G = (V, E).
Set U = E.
Create a set consisting of each edge incident to v.
Direct correspondence between IS and SP.
IS ≥ k ⇐⇒ SP ≥ k
9/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
A clause Cj is a disjunction of (distinct) terms, e.g., (x1 ∨ x2).
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
A clause Cj is a disjunction of (distinct) terms, e.g., (x1 ∨ x2). Length of Cj is the # of terms in Cj.
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
A clause Cj is a disjunction of (distinct) terms, e.g., (x1 ∨ x2). Length of Cj is the # of terms in Cj.
A collection/conjunction of k clauses: C : C1 ∧ C2 ∧ · ∧ Ck .
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
A clause Cj is a disjunction of (distinct) terms, e.g., (x1 ∨ x2). Length of Cj is the # of terms in Cj.
A collection/conjunction of k clauses: C : C1 ∧ C2 ∧ · ∧ Ck .
Truth assignment function v : X → {0, 1}, assigns values to the terms and returns the conjunction of the clauses.
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
A clause Cj is a disjunction of (distinct) terms, e.g., (x1 ∨ x2). Length of Cj is the # of terms in Cj.
A collection/conjunction of k clauses: C : C1 ∧ C2 ∧ · ∧ Ck .
Truth assignment function v : X → {0, 1}, assigns values to the terms and returns the conjunction of the clauses.
v is a satisfying assignment if C is 1, i.e., all Ci evaluate to 1.
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Satisfiability Problem (SAT)
TH4: What values will satisfy the example?
(x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3)
Preliminaries
A set of boolean terms/literals: X : x1, . . . , xn.
For a given variable xi, xi is the assigned value and xi is the negation of the assigned value.
A clause Cj is a disjunction of (distinct) terms, e.g., (x1 ∨ x2). Length of Cj is the # of terms in Cj.
A collection/conjunction of k clauses: C : C1 ∧ C2 ∧ · ∧ Ck .
Truth assignment function v : X → {0, 1}, assigns values to the terms and returns the conjunction of the clauses.
v is a satisfying assignment if C is 1, i.e., all Ci evaluate to 1.
10/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Three Satifiability (3SAT)
SAT Problem
Given a set of literals: X : x1, . . . , xn, and a collection of clauses
C : C1 ∧ C2 ∧ · ∧ Ck , does there exist a satisfying assignment?
11/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Three Satifiability (3SAT)
3SAT Problem
Given a set of literals: X : x1, . . . , xn, and a collection of clauses C : C1 ∧ C2 ∧ · ∧ Ck , each of length 3, does there exist a satisfying assignment?
11/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Three Satifiability (3SAT)
3SAT Problem
Given a set of literals: X : x1, . . . , xn, and a collection of clauses C : C1 ∧ C2 ∧ · ∧ Ck , each of length 3, does there exist a satisfying assignment?
Gadgets
Gadgets are often used to show Y ≤p X.
A subset of problem X that represents a component of problem Y.
11/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Three Satifiability (3SAT)
3SAT Problem
Given a set of literals: X : x1, . . . , xn, and a collection of clauses C : C1 ∧ C2 ∧ · ∧ Ck , each of length 3, does there exist a satisfying assignment?
Gadgets
Gadgets are often used to show Y ≤p X.
A subset of problem X that represents a component of problem Y.
A procedure to convert some of the components of Y to a piece of problem X.
11/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
Assume we have a black-box solver for IS.
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
Assume we have a black-box solver for IS. Transfer any 3SAT to IS:
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
Assume we have a black-box solver for IS. Transfer any 3SAT to IS:
Clause gadget: k3 graph
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
Assume we have a black-box solver for IS. Transfer any 3SAT to IS:
Clause gadget: k3 graph
Add an edge between vij = xq and all vitjt = xq.
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
IS of size ≥ k ⇐⇒ 3SAT is satisfiable.
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
IS of size ≥ k ⇐⇒ 3SAT is satisfiable.
Each node in IS represents a 1 assignment.
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
IS of size ≥ k ⇐⇒ 3SAT is satisfiable.
Each node in IS represents a 1 assignment. Within each gadget, only 1 node can be in IS.
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT to Independent Set (IS)
Theorem 4
3SAT ≤p IS
Proof.
IS of size ≥ k ⇐⇒ 3SAT is satisfiable.
Each node in IS represents a 1 assignment. Within each gadget, only 1 node can be in IS.
Conflict edges prevent xi and xi both being assigned 1.
12/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Transitivity of Reductions
Observation 1
If Z ≤p Y, and Y ≤p X, then Z ≤p X.
13/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Transitivity of Reductions
Observation 1
If Z ≤p Y, and Y ≤p X, then Z ≤p X.
So,
13/40
3SAT ≤p IS ≤p VC ≤p SC
3SAT ≤p IS ≤p SP VC ≤p IS ≤p SP .
and
and
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
NP
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Input Formalization
For a problem instance:
Let s be a binary string that encodes the input.
|s| is the length of s, i.e., the # of bits in s.
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Input Formalization
For a problem instance:
Let s be a binary string that encodes the input.
|s| is the length of s, i.e., the # of bits in s.
Polynomial Run-Time
Algorithm A has a polynomial run-time if run-time is O(poly(|s|))
in the worst-case, where poly(·) is a polynomial function.
Complexity class P
P is the set of all problems for which there exists an algorithm A
that solves the problem with polynomial run-time.
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Efficient Certification
Certifier B(s, t) for a problem P: s is an input instance of P.
t is a certificate; a proof that s is a yes-instance.
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Efficient Certification
Certifier B(s, t) for a problem P: s is an input instance of P.
t is a certificate; a proof that s is a yes-instance. Efficient:
For every s, we have s ∈ P iff there exists a t, |t| ≤ poly(|s|), for which B(s, t) returns yes.
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Efficient Certification
Certifier B(s, t) for a problem P: s is an input instance of P.
t is a certificate; a proof that s is a yes-instance. Efficient:
For every s, we have s ∈ P iff there exists a t, |t| ≤ poly(|s|), for which B(s, t) returns yes.
In other words, using t, we can check if s is a yes-instance in polynomial time.
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Efficient Certification
Certifier B(s, t) for a problem P: s is an input instance of P.
t is a certificate; a proof that s is a yes-instance. Efficient:
For every s, we have s ∈ P iff there exists a t, |t| ≤ poly(|s|), for which B(s, t) returns yes.
In other words, using t, we can check if s is a yes-instance in polynomial time.
B(s, t) returning no does not mean that s is a no-instance
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Efficient Certification
Certifier B(s, t) for a problem P: s is an input instance of P.
t is a certificate; a proof that s is a yes-instance. Efficient:
For every s, we have s ∈ P iff there exists a t, |t| ≤ poly(|s|), for which B(s, t) returns yes.
In other words, using t, we can check if s is a yes-instance in polynomial time.
B(s, t) returning no does not mean that s is a no-instance… only that t is not a valid proof.
14/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Efficient Certification
Efficient Certification
Certifier B(s, t) for a problem P: s is an input instance of P.
t is a certificate; a proof that s is a yes-instance. Efficient:
For every s, we have s ∈ P iff there exists a t, |t| ≤ poly(|s|), for which B(s, t) returns yes.
In other words, using t, we can check if s is a yes-instance in polynomial time.
B(s, t) returning no does not mean that s is a no-instance… only that t is not a valid proof.
B(s, t) provides a brute-force algorithm: For a given s, check every possible t.
14/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
NP Problems
Complexity Class NP
Non-deterministic, Polynomial time: can be solved in polynomial time by testing every t simultaneously (non-deterministic).
Set of all problems for which there exists an efficient certifier.
15/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
NP Problems
Complexity Class NP
Non-deterministic, Polynomial time: can be solved in polynomial time by testing every t simultaneously (non-deterministic).
Set of all problems for which there exists an efficient certifier.
Theorem 5
P ⊆ NP
15/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
NP Problems
Complexity Class NP
Non-deterministic, Polynomial time: can be solved in polynomial time by testing every t simultaneously (non-deterministic).
Set of all problems for which there exists an efficient certifier.
Theorem 5
P ⊆ NP
Proof.
TH5: Which proof technique?
15/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
NP Problems
Complexity Class NP
Non-deterministic, Polynomial time: can be solved in polynomial time by testing every t simultaneously (non-deterministic).
Set of all problems for which there exists an efficient certifier.
Theorem 5
P ⊆ NP
Proof.
For every p ∈ P, ∃ an algorithm A that runs in polynomial time.
B(s, t) for any t returns A(s).
15/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Million Dollar Question: P vs NP
1 of 7 Clay Mathematics Institute Millennium Prize Problems
16/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
NP-complete
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Hardest NP Problems
NP-Hard
Problem X is NP-Hard if: For all Y ∈ NP, Y ≤p X.
NP-Hard problem may or may not be in NP.
17/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Hardest NP Problems
NP-Hard
Problem X is NP-Hard if: For all Y ∈ NP, Y ≤p X.
NP-Hard problem may or may not be in NP.
NP-Complete
Problem X is NP-Complete if: For all Y ∈ NP, Y ≤p X. X is in NP.
17/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Million Dollar Question: P vs NP
1 of 7 Clay Mathematics Institute Millennium Prize Problems
18/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Hardest NP Problems
NP-Hard
Problem X is NP-Hard if: For all Y ∈ NP, Y ≤p X.
NP-Hard problem may or may not be in NP.
NP-Complete
Problem X is NP-Complete if: For all Y ∈ NP, Y ≤p X. X is in NP.
19/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Hardest NP Problems
NP-Complete
Problem X is NP-Complete if: For all Y ∈ NP, Y ≤p X. X is in NP.
Theorem 6
Suppose X ∈ NP-Complete. Then, X is solvable in polynomial time iff
P = NP.
19/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Hardest NP Problems
NP-Complete
Problem X is NP-Complete if: For all Y ∈ NP, Y ≤p X. X is in NP.
Theorem 6
Suppose X ∈ NP-Complete. Then, X is solvable in polynomial time iff
P = NP.
Proof.
⇐: Suppose P = NP, then by definition of P, X can be solved in polynomial time.
19/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Hardest NP Problems
NP-Complete
Problem X is NP-Complete if: For all Y ∈ NP, Y ≤p X. X is in NP.
Theorem 6
Suppose X ∈ NP-Complete. Then, X is solvable in polynomial time iff
P = NP.
Proof.
⇒: Suppose X can be solved in polynomial time. Then, by definition of NP-Complete, all problems ∈ NP ≤p X. Hence, solvable in polynomial time and ∈ P.
19/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Stephen Cook (1968)
20/40
Leonid Levin (2010)
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
Circuit k:
A DAG (nodes have 0, 1, or 2 incoming edges).
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
Circuit k:
A DAG (nodes have 0, 1, or 2 incoming edges).
Source: Nodes with no incoming edges; may have a preset binary value.
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
Circuit k:
A DAG (nodes have 0, 1, or 2 incoming edges).
Source: Nodes with no incoming edges; may have a preset binary value.
Every other node is
labelled with a gate.
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
Circuit k:
A DAG (nodes have 0, 1, or 2 incoming edges).
Source: Nodes with no incoming edges; may have a preset binary value.
Every other node is
labelled with a gate. Output: Result of the node with no outgoing edges.
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
TH6: What is the output with an input of (1, 0, 0)?
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
Circuit k:
A DAG (nodes have 0, 1, or 2 incoming edges).
Source: Nodes with no incoming edges; may have a preset binary value.
Every other node is
labelled with a gate. Output: Result of the node with no outgoing edges.
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
TH7: Give an input that satisfies the example.
Circuit Satisfiability Problem (CSAT)
Problem Definition
3 types of gates: ∧ (AND),
∨ (OR), and ¬ (NOT).
Circuit k:
A DAG (nodes have 0, 1, or 2 incoming edges).
Source: Nodes with no incoming edges; may have a preset binary value.
Every other node is
labelled with a gate. Output: Result of the node with no outgoing edges.
21/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
1
Show that CSAT ∈ NP:
Input size is Ω(|V|).
A single gate can be evaluated in constant time.
Evaluate a certificate of the inputs can be verified in O(|V|)
time.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. We need to show X ≤p CSAT.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. We need to show X ≤p CSAT.
By definition for X:
X has an input of |s| bits. Produces 1 bit of output (yes/no).
∃ an efficient certifier BX (·, ·).
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. Reduction to CSAT:
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. Reduction to CSAT:
Output is 1 when X is yes; otherwise 0.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. Reduction to CSAT:
Output is 1 when X is yes; otherwise 0. Sources: |s| + |t| = n + poly(n) bits.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. Reduction to CSAT:
Output is 1 when X is yes; otherwise 0. Sources: |s| + |t| = n + poly(n) bits.
The first n bits are hard-coded to the X instance input.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. Reduction to CSAT:
Output is 1 when X is yes; otherwise 0. Sources: |s| + |t| = n + poly(n) bits.
The first n bits are hard-coded to the X instance input. The poly(n) bits are free and used to find a t such that BX (s, t) is yes.
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
First NP-Complete Problem
Theorem 6
Cook (1971) – Levin (1973) Theorem [Paraphrase]: Circuit Satisfiability Problem (CSAT) is NP-Complete.
Partial Proof.
Show that CSAT ∈ NP:
1
2
Reduce every problem ∈ NP to CSAT:
Consider an arbitrary problem X ∈ NP. Reduction to CSAT:
Output is 1 when X is yes; otherwise 0. Sources: |s| + |t| = n + poly(n) bits.
The first n bits are hard-coded to the X instance input. The poly(n) bits are free and used to find a t such that BX (s, t) is yes.
The gates of the circuit are a translation of algorithm BX .
22/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Example: Independent Set (k ≥ 2) as Circuit Satisfiability Problem.
23/40
IntractabilityReductions
-completeTaxonomy
NPNP coNPPSPACE
Example: Independent Set (k ≥ 2) as Circuit Satisfiability Problem.
TH8: Draw the underlying Independent Set graph.
23/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Strategies for Proving NP-Completeness
Showing that Problem X is NP-Complete Cook Reduction:
Prove that X ∈ NP.
24/40
Choose a problem Y ∈ NP-Complete.
1
2
3
Prove Y ≤p X.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Strategies for Proving NP-Completeness
Showing that Problem X is NP-Complete Cook Reduction:
Prove that X ∈ NP.
Choose a problem Y ∈ NP-Complete.
1
2
3
Prove Y ≤p X.
Typical Step 3
3
24/40
Karp Reduction: For an arbitrary instance sY of Y, show
how to construct, in polynomial time, an instance sX of X
such that sy is a yes iff sx is a yes.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Theorem 7
3SAT is NP-Complete.
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Theorem 7
3SAT is NP-Complete.
Exercise: Do step 1.
Show that Problem 3SAT is NP-Complete Cook Reduction:
Prove that 3SAT ∈ NP.
25/40
Choose a problem Y ∈ NP-Complete.
1
2
3
Prove Y ≤p 3SAT.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Theorem 7
3SAT is NP-Complete.
Show that Problem 3SAT is NP-Complete Cook Reduction:
Prove that 3SAT ∈ NP.
Choose a problem Y ∈ NP-Complete.
1
2
3
Prove Y ≤p 3SAT.
Proof.
1
can be verified in polynomial time.
25/40
Use a truth assignment of the literals as a certificate. This
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Theorem 7
3SAT is NP-Complete.
Show that Problem 3SAT is NP-Complete Cook Reduction:
Prove that 3SAT ∈ NP.
Choose a problem Y ∈ NP-Complete.
1
2
3
Prove Y ≤p 3SAT.
Proof.
1
2
25/40
Use a truth assignment of the literals as a certificate. This can be verified in polynomial time.
The only NP-Complete problem we know is CSAT.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
25/40
For an arbitrary circuit k:
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
→ 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
OR: → 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
Let u, w be the inputs. We need xv = xu ∨ xw .
→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
OR: → 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
Let u, w be the inputs. We need xv = xu ∨ xw .
AND:→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
Let u, w be the inputs. We need xv = xu ∧ xw .
→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
OR: → 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
Let u, w be the inputs. We need xv = xu ∨ xw .
AND:→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
Let u, w be the inputs. We need xv = xu ∧ xw .
For each → 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
constant source s:
→ 1 clause: (xs) if 1, and (xs) if 0.
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
OR: → 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
Let u, w be the inputs. We need xv = xu ∨ xw .
AND:→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
Let u, w be the inputs. We need xv = xu ∧ xw .
For each → 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
constant source s:
For t→he 1 clause: (xs) if 1, and (xs) if 0. output o: 1 clause (xo).
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
OR: → 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
Let u, w be the inputs. We need xv = xu ∨ xw .
AND:→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
Let u, w be the inputs. We need xv = xu ∧ xw .
For each → 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
constant source s:
→ 1 clause: (xs) if 1, and (xs) if 0.
For the output o: 1 clause (xo).
Convert clauses to length 3:
We need 2 variables z1 and z2 that are always 0 in a satisfying assignment.
To ensure this, we need 4 variables: z1, z2, z3, z4.
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
Proof.
3
For an arbitrary circuit k:
Each node v is assigned a variable xv.
For each gate:
NOT: Let u be the input. We need xu = xv .
OR: → 2 clauses: (xv ∨ xu) ∧ (xv ∨ xu).
Let u, w be the inputs. We need xv = xu ∨ xw .
AND:→ 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
Let u, w be the inputs. We need xv = xu ∧ xw .
For each → 3 clauses: (xv ∨ xu) ∧ (xv ∨ xw ) ∧ (xv ∨ xu ∨ xw ).
constant source s:
For t→he 1 clause: (xs) if 1, and (xs) if 0. Conv output o: 1 clause (xo).
ert clauses to length 3:
4 variables: z1, z2, z3, z4, and 8 clauses for i ∈ {1, 2}:
(zi ∨ z3 ∨ z4) ∧ (zi ∨ z3 ∨ z4) ∧ (zi ∨ z3 ∨ z4) ∧ (zi ∨ z3 ∨ z4).
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT is NP-Complete
From our previous reductions
3SAT ≤p IS ≤p VC ≤p SC
and
3SAT ≤p IS ≤p SP
and the fact that 3SAT is NP-Complete:
Corollary 7
The following problems are NP-Complete:
3SAT, IS, VC, SC, SP .
25/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
TNaPx-ocnoommplyeotefness
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Sequencing Problems
Travelling Salesperson Problem (TSP)
A salesperson must visit n
cities v1, v2, . . . , vn.
Starting at some v1, visit all cities and return to v1.
Distance function: d(·, ·) for all pairs of cities (not necessarily symmetric nor metric).
Optimization: What is the shortest tour?
26/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Sequencing Problems
Travelling Salesperson Problem (TSP)
A salesperson must visit n
cities v1, v2, . . . , vn.
Starting at some v1, visit all cities and return to v1.
Distance function: d(·, ·) for all pairs of cities (not necessarily symmetric nor metric).
Decision: Is there a tour of
length D?
26/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Sequencing Problems
Travelling Salesperson Problem (TSP)
A salesperson must visit n
cities v1, v2, . . . , vn.
Starting at some v1, visit all cities and return to v1.
Distance function: d(·, ·)
for all pairs of cities (not necessarily symmetric nor metric).
Hamiltonian Cycle
Graph analogue of TSP.
Hamiltonian cycle: a tour of
cycle?
26/40
the nodes of G that visits each node once.
Given a digraph G, does it contain a Hamiltonian
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Sequencing Problems
Travelling Salesperson Problem (TSP)
A salesperson must visit n
cities v1, v2, . . . , vn.
Starting at some v1, visit all cities and return to v1.
Distance function: d(·, ·)
for all pairs of cities (not necessarily symmetric nor metric).
TH9: Does this graph contain a Hamiltonian cycle?
Hamiltonian Cycle
Graph analogue of TSP.
Hamiltonian cycle: a tour of
cycle?
26/40
the nodes of G that visits each node once.
Given a digraph G, does it contain a Hamiltonian
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT ≤p Hamiltonian
Theorem 8
Hamiltonian Cycle is NP-complete.
Proof.
1
2
In NP: A certificate would be a sequence of vertices which can be verified in polynomial time.
Choose an NP-complete problem: 3SAT.
27/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT ≤p Hamiltonian
Theorem 8
Hamiltonian Cycle is NP-complete.
Proof.
3
3SAT ≤p Hamiltonian:
Pi (containing 3k + 2 nodes) for each Xi : left traversal for 1 and right traversal for 0.
27/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3SAT ≤p Hamiltonian
Theorem 8
Hamiltonian Cycle is NP-complete.
Proof.
3
3SAT ≤p Hamiltonian:
Ci for each clause i: Connect based on xi or xi .
27/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
28/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
1
28/40
In NP: Certificate that is a tour of the cities.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
1
2
28/40
In NP: Certificate that is a tour of the cities. TH10: Which NP-complete problem?
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
In NP: Certificate that is a tour of the cities. Use Hamiltonian Cycle.
1
2
3
28/40
Hamiltonian Cycle ≤p TSP:
Exo: Try to come up with the reduction.
IntractabilityReductions
NPNP -completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
In NP: Certificate that is a tour of the cities. Use Hamiltonian Cycle.
1
2
3
28/40
Hamiltonian Cycle ≤p TSP:
Given a graph G = (V, E):
IntractabilityReductions
NPNP -completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
In NP: Certificate that is a tour of the cities. Use Hamiltonian Cycle.
1
2
3
Hamiltonian Cycle ≤p TSP:
Given a graph G = (V, E):
For each v, make a city.
28/40
IntractabilityReductions
NPNP -completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
In NP: Certificate that is a tour of the cities. Use Hamiltonian Cycle.
1
2
3
Hamiltonian Cycle ≤p TSP:
Given a graph G = (V, E):
For each v, make a city.
For each edge (u, v) ∈ E, define d(u, v) = 1.
28/40
IntractabilityReductions
NPNP -completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
In NP: Certificate that is a tour of the cities. Use Hamiltonian Cycle.
1
2
3
Hamiltonian Cycle ≤p TSP:
Given a graph G = (V, E):
For each v, make a city.
For each edge (u, v) ∈ E, define d(u, v) = 1. For each pair (u, v) ∈/ E, define d(u, v) = 2.
28/40
IntractabilityReductions
NPNP -completeTaxonomy
coNPPSPACE
Travelling Salesperson
Theorem 9
Travelling Salesperson (TSP) is NP-complete.
Proof.
In NP: Certificate that is a tour of the cities. Use Hamiltonian Cycle.
1
2
3
Hamiltonian Cycle ≤p TSP:
Given a graph G = (V, E):
For each v, make a city.
For each edge (u, v) ∈ E, define d(u, v) = 1. For each pair (u, v) ∈/ E, define d(u, v) = 2. Set the tour bound to be n.
28/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Exercise: Show that Hamiltonian Path is NP-complete
Hamiltonian Path
A simple path in a digraph G that contains all nodes. Another sequencing problem.
29/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Exercise: Show that Hamiltonian Path is NP-complete
Theorem 10
Hamiltonian Path is NP-complete
Proof.
1
In NP: Certificate is a path in G which can be verified in
2
29/40
polynomial time.
NP-complete problem: Hamiltonian Cycle.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Exercise: Show that Hamiltonian Path is NP-complete
Theorem 10
Hamiltonian Path is NP-complete
Proof.
3
29/40
Hamiltonian Cycle ≤p Hamiltonian Path:
For G = (V, E) create Gj:
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Exercise: Show that Hamiltonian Path is NP-complete
Theorem 10
Hamiltonian Path is NP-complete
Proof.
3
Hamiltonian Cycle ≤p Hamiltonian Path:
For G = (V, E) create Gj:
Choose an arbitrary v ∈ V: Vj = V \ {v} ∪ {vj, vjj}.
29/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Exercise: Show that Hamiltonian Path is NP-complete
Theorem 10
Hamiltonian Path is NP-complete
Proof.
3
Hamiltonian Cycle ≤p Hamiltonian Path:
For G = (V, E) create Gj:
Choose an arbitrary v ∈ V: Vj = V \ {v} ∪ {vj, vjj}. Initialize Ej = E:
For each edge (v, w) ∈ E: Ej \ {(v, w)} ∪ {(vj, w)}.
For each edge (u, v) ∈ E: Ej \ {(u, v)} ∪ {(u, vjj)}.
29/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Exercise: Show that Hamiltonian Path is NP-complete
Theorem 10
Hamiltonian Path is NP-complete
Proof.
3
Hamiltonian Cycle ≤p Hamiltonian Path:
For G = (V, E) create Gj:
Choose an arbitrary v ∈ V: Vj = V \ {v} ∪ {vj, vjj}. Initialize Ej = E:
For each edge (v, w) ∈ E: Ej \ {(v, w)} ∪ {(vj, w)}.
For each edge (u, v) ∈ E: Ej \ {(u, v)} ∪ {(u, vjj)}.
A path vj → vjj means Hamiltonian Cycle.
29/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Partitioning Problems
3-D Matching
Given 3 disjoint sets: X, Y, Z (each of size n). A set of m ≥ n trebles T ⊆ X × Y × Z.
Does there exist a set of n trebles from T so that each item is in exactly one of these trebles?
30/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
1
2
31/40
In NP: Certificate is a set of trebles which can be verified in polynomial time.
TH11: Which NP-complete problem?
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
1
2
31/40
In NP: Certificate is a set of trebles which can be verified in polynomial time.
Use 3SAT.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
3
3SAT ≤p 3-D Matching:
Consider an arbitrary 3SAT:
Variable xi gadget:
Core:
i
i 1
i
2k
A = {a , . . . , a }.
Tips:
i
i
i 1 2k
B = {b , . . . , b }.
j j j+1 j
ti = (ai, ai , bi ) for
j = 1, 2, . . . , 2k (add mod 2k).
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
3
3SAT ≤p 3-D Matching:
Consider an arbitrary 3SAT:
Clause Cj gadget:
j
j j j j
j i
j 2j i
Add P = {p , p } with trebles: (p , p , b ) if x and
(Pj, Pjj, bi
2j+1
) if xi .
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
3
3SAT ≤p 3-D Matching:
Consider an arbitrary 3SAT:
Counting cores: covered by even/odd choice.
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
3
3SAT ≤p 3-D Matching:
Consider an arbitrary 3SAT:
Counting cores: covered by even/odd choice. Counting tips: n2k
Even/odd tips cover nk. Clauses cover k.
(n − 1)k uncovered.
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
3
3SAT ≤p 3-D Matching:
Consider an arbitrary 3SAT:
Counting cores: covered by even/odd choice. Counting tips: n2k
Even/odd tips cover nk. Clauses cover k.
(n − 1)k uncovered.
Clean-up gadget:
Qi = {qi, qji } with treble (qi, qji , b) for every tip b.
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-D Matching is NP-Complete
Theorem 11
3-D Matching is NP-Complete.
Proof.
3
3SAT ≤p 3-D Matching:
Consider an arbitrary 3SAT:
Counting cores: covered by even/odd choice. Counting tips: n2k
Even/odd tips cover nk. Clauses cover k.
(n − 1)k uncovered.
Clean-up gadget:
Qi = {qi, qji } with treble (qi, qji , b) for every tip b.
What are the 3 sets?
X = {a
j even
j
} ∪ {p } ∪ {
i
i i
j odd
j
j
q },Y = {a } ∪ {p } ∪ {
j
i
q },Z = {
i
j
b }.
31/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Graph Colouring
Problem
Given a graph G and a bound k, does
G have a k-colouring?
32/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Graph Colouring
Problem
Given a graph G and a bound k, does
G have a k-colouring?
k-Colour
Colouring of the nodes of a graph such that no adjacent nodes have the same colour, using at most k colours.
32/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Graph Colouring
Problem
Given a graph G and a bound k, does
G have a k-colouring?
k-Colour
Colouring of the nodes of a graph such that no adjacent nodes have the same colour, using at most k colours.
Labelling (partitioning) function f : V → {1, . . . , k} such that, for every (u, v) ∈ E, f (u) ƒ= f (v).
32/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
33/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
1
2
33/40
In NP: Certificate is a colouring of the nodes which can be verified in polynomial time.
TH12: Which NP-complete problem?
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
1
2
33/40
In NP: Certificate is a colouring of the nodes which can be verified in polynomial time.
NP-complete problem: 3SAT.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
3
33/40
3SAT ≤p 3 Colouring:
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
3
3SAT ≤p 3 Colouring:
For each literal: Nodes vi and vi .
33/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
3
3SAT ≤p 3 Colouring:
For each literal: Nodes vi and vi .
Nodes T (true), F (false), and B (base).
33/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
3
3SAT ≤p 3 Colouring:
For each literal: Nodes vi and vi .
Nodes T (true), F (false), and B (base). Edges: (vi, vi ),(vi, B),(vi, B).
33/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
3
3SAT ≤p 3 Colouring:
For each literal: Nodes vi and vi .
Nodes T (true), F (false), and B (base). Edges: (vi, vi ),(vi, B),(vi, B).
Edges: (T, F),(F, B),(T, B).
33/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
3-Colouring is NP-Complete
Theorem 12
3-Colouring is NP-Complete.
Proof.
3
3SAT ≤p 3 Colouring:
For each clause:
33/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Numerical Problems
Subset Sum Problem
Given a set of n natural numbers {w1, . . . , wn} and a target W, is there a subset of the numbers that add up to W?
34/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Numerical Problems
Subset Sum Problem
Given a set of n natural numbers {w1, . . . , wn} and a target W, is there a subset of the numbers that add up to W?
Dynamic Programming Approach
We saw an O(nW) algorithm.
Pseudo-polynomial: W is unbounded, e.g., 2n.
34/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
1
2
35/40
In NP: Certificate is a subset of the numbers which can be verified in polynomial time.
TH13: Which NP-complete problem?
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
1
2
35/40
In NP: Certificate is a subset of the numbers which can be verified in polynomial time.
NP-complete problem: 3-D Matching.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
35/40
3-D Matching ≤p Subset Sum: Exercise: Try it, but tough.
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
3-D Matching ≤p Subset Sum:
3-D Matching: Subsets can be viewed as length 3n bit vectors with a 1 indicating that item is in the set.
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
3-D Matching ≤p Subset Sum:
3-D Matching: Subsets can be viewed as length 3n bit vectors with a 1 indicating that item is in the set.
For each treble (i, j, k) from X × Y × Z construct a wt:
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
3-D Matching ≤p Subset Sum:
3-D Matching: Subsets can be viewed as length 3n bit vectors with a 1 indicating that item is in the set.
For each treble (i, j, k) from X × Y × Z construct a wt:
A digits with 1 at i, n + j, and 2n + k.
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
3-D Matching ≤p Subset Sum:
3-D Matching: Subsets can be viewed as length 3n bit vectors with a 1 indicating that item is in the set.
For each treble (i, j, k) from X × Y × Z construct a wt:
A digits with 1 at i, n + j, and 2n + k. For base d, wt = di−1 + dn+j−1 + d2n+k−1.
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
3-D Matching ≤p Subset Sum:
3-D Matching: Subsets can be viewed as length 3n bit vectors with a 1 indicating that item is in the set.
For each treble (i, j, k) from X × Y × Z construct a wt:
A digits with 1 at i, n + j, and 2n + k. For base d, wt = di−1 + dn+j−1 + d2n+k−1.
Set base d = m + 1 to avoid addition carry overs.
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Subset Sum is NP-Complete
Theorem 13
Subset Sum is NP-Complete.
Proof.
3
3-D Matching ≤p Subset Sum:
3-D Matching: Subsets can be viewed as length 3n bit vectors with a 1 indicating that item is in the set.
For each treble (i, j, k) from X × Y × Z construct a wt:
A digits with 1 at i, n + j, and 2n + k. For base d, wt = di−1 + dn+j−1 + d2n+k−1.
Set base d = m + 1 to avoid addition carry overs.
Σ
3n−1
i
Set W = (m + 1) which corresponds to have each
item exactly0 once.
35/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Taxonomy of Hard Problems
Packing Problems Independent Set Set Packing
Covering Problems
Vertex Cover Set Cover
Sequencing Problems
TSP
Hamiltonian Cycle Hamiltonian Path
36/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Taxonomy of Hard Problems
Partitioning Problems 3-D Matching Graph Colouring
Numerical Problems Subset Sum Knapsack
Constraint Satisfaction Problems
3SAT
36/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Asymmetry of NP
Efficient Certifier Asymmetry
Given an instance s of problem X:
For any t, B(s, t) = yes implies yes-instance. For all t, B(s, t) = no implies no-instance.
37/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Asymmetry of NP
Efficient Certifier Asymmetry
Given an instance s of problem X:
For any t, B(s, t) = yes implies yes-instance. For all t, B(s, t) = no implies no-instance.
Complimentary Problem
For every problem X, there is a complementary problem X: For all input s, s ∈ X iff s ∈/ X.
37/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Asymmetry of NP
Efficient Certifier Asymmetry
Given an instance s of problem X:
For any t, B(s, t) = yes implies yes-instance. For all t, B(s, t) = no implies no-instance.
Complimentary Problem
For every problem X, there is a complementary problem X: For all input s, s ∈ X iff s ∈/ X.
Note that, if X ∈ P, then X ∈ P.
37/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
Open Question
Does NP = coNP?
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
Open Question
Does NP = coNP?
Theorem 14
If NP ƒ= coNP, then P ƒ= NP.
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
Open Question
Does NP = coNP?
Theorem 14
If NP ƒ= coNP, then P ƒ= NP.
Proof.
Contra-positive: Prove it!
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
Open Question
Does NP = coNP?
Theorem 14
If NP ƒ= coNP, then P ƒ= NP.
Proof.
Contra-positive: Assume P = NP:
X ∈ NP → X ∈ P → X ∈ P → X ∈ NP → X ∈ coNP.
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
Open Question
Does NP = coNP?
Theorem 14
If NP ƒ= coNP, then P ƒ= NP.
Proof.
Contra-positive: Assume P = NP:
X ∈ NP → X ∈ P → X ∈ P → X ∈ NP → X ∈ coNP.
X ∈ coNP → X ∈ NP → X ∈ P → X ∈ P → X ∈ NP.
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
coNP
Complexity Class coNP
A problem X ∈ coNP iff X ∈ NP.
Open Question
Does NP = coNP?
Theorem 14
If NP ƒ= coNP, then P ƒ= NP.
Open Question
Does P = NP ∩ coNP?
38/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
PSPACE
IntractabilityReductions
NPNP -completeTaxonomy coNPPSPACE
Beyond Time
Complexity Class PSPACE
Set of all problems that can be solved using polynomial space.
39/40
IntractabilityReductions
NPNP -completeTaxonomy coNPPSPACE
Beyond Time
Complexity Class PSPACE
Set of all problems that can be solved using polynomial space.
Theorem 15
P ⊆ PSPACE
39/40
IntractabilityReductions
NPNP -completeTaxonomy coNPPSPACE
Beyond Time
Complexity Class PSPACE
Set of all problems that can be solved using polynomial space.
Theorem 15
P ⊆ PSPACE
Theorem 16
NP ⊆ PSPACE
39/40
IntractabilityReductions
NPNP -completeTaxonomy coNPPSPACE
Beyond Time
Complexity Class PSPACE
Set of all problems that can be solved using polynomial space.
Theorem 15
P ⊆ PSPACE
Theorem 16
NP ⊆ PSPACE
Proof.
For 3SAT, a bit vector can encode an assignment.
We can try all bit vectors with one n-length vector in memory:
Start with 0 until 2n − 1, adding 1 at each iteration.
39/40
IntractabilityReductions
NPNP -completeTaxonomy coNPPSPACE
Beyond Time
Complexity Class PSPACE
Set of all problems that can be solved using polynomial space.
Theorem 15
P ⊆ PSPACE
Theorem 16
NP ⊆ PSPACE
Proof.
For 3SAT, a bit vector can encode an assignment.
We can try all bit vectors with one n-length vector in memory:
Start with 0 until 2n − 1, adding 1 at each iteration.
Since 3SAT ∈ PSPACE and is NP-complete, for any Y ∈ NP,
Y ≤p 3SAT and solve in PSPACE.
39/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Prototypical PSPACE Problem
40/40
Let Φ(x1, . . . , xn) be a conjunction of k disjunction of n variables (like SAT).
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Prototypical PSPACE Problem
Let Φ(x1, . . . , xn) be a conjunction of k disjunction of n variables (like SAT).
Quantified SAT
∃x1∀x2∃x3 · · · QnxnΦ(x1, . . . , xn) (Prenex normal form). Contingency planning.
40/40
IntractabilityReductions
NPNP
-completeTaxonomy
coNPPSPACE
Prototypical PSPACE Problem
Let Φ(x1, . . . , xn) be a conjunction of k disjunction of n variables (like SAT).
Quantified SAT
∃x1∀x2∃x3 · · · QnxnΦ(x1, . . . , xn) (Prenex normal form). Contingency planning.
Theorem 17
QSAT is PSPACE-complete.
40/40