THE UNIVERSITY OF NEW SOUTH WALES
11. INTRACTABILITY
Raveen de Silva,
office: K17 202
Course Admin: ,
School of Computer Science and Engineering UNSW Sydney
Term 3, 2021
Table of Contents
1. Feasibility of Algorithms 2. Polynomial Reductions 3. Optimisation Problems 4. Puzzle
Polynomial Time Algorithms
Definition
A (sequential) algorithm is said to be polynomial time if for every input it terminates in polynomially many steps in the length of the input.
This means that there exists a natural number k (independent of the input) so that the algorithm terminates in T(n) = O(nk) many steps, where n is the size of the input.
Length of Input
Question
What is the length of an input?
Answer
It is the number of symbols needed to describe the input precisely.
Length of Input: Integers
For example, if input x is an integer, then |x| can be taken to be the number of bits in the binary representation of x.
As we will see, the definition of polynomial time computability is quite robust with respect to how we represent inputs.
For example, we could instead define the length of an integer x as the number of digits in the decimal representation of x.
This can only change the constants involved in the expression T(n) = O(nk) but not the asymptotic bound.
Length of Input: Weighted Graphs
If the input is a weighted graph G, then G can be described using its adjacency list: for each vertex vi , store a list of edges incident to vi together with their (integer) weights represented in binary.
Alternatively, we can represent G with its adjacency matrix. If the input graphs are all sparse, this can unnecessarily
increase the length of the representation of the graph.
However, since we are interested only in whether the algorithm runs in polynomial time and not in the particular degree of the polynomial bounding such a run time, this does not matter.
In fact, every precise description without artificial redundancies will do.
Decision Problems and Class P
Definition
A decision problem is a problem with a YES or NO answer.
Examples include:
“Input number n is a prime number.”
“Input graph G is connected.”
“Input graph G has a cycle containing all vertices of G.”
Definition
A decision problem A(x) is in class P (polynomial time, denoted A ∈ P) if there exists a polynomial time algorithm which solves it (i.e. produces the correct output for each input x).
Class NP
Definition
A decision problem A(x) is in class NP (non-deterministic polynomial time, denoted A ∈ NP) if there exists a problem B(x, y) such that
1. for every input x, A(x) is true if and only if there is some y for which B(x, y) is true, and
2. the truth of B(x,y) can be verified by an algorithm running in polynomial time in the length of x only.
We call y a certificate for x.
Example: Primality Testing
Question
Consider the decision problem A(x) =“integer x is not prime”. Is A ∈ NP?
Answer
We need to find a problem B(x,y) such that A(x) is true if and only if there is some y for which B(x,y) is true.
The natural choice is B(x,y) =“x is divisible by y”.
B(x,y) can indeed be verified by an algorithm running in time polynomial in the length of x only.
Example: Primality Testing
Question
Is A ∈ P?
Answer
Also yes! But this is not at all straightforward. This is a famous and unexpected result, proved in 2002 by the Indian computer scientists Agrawal, Kayal and Saxena.
The AKS algorithm provides a deterministic, polynomial time procedure for testing whether an integer x is prime.
Example: Primality Testing
The length of the input for primality testing is O(logx). Comparing some well-known algorithms for primality testing:
The na ̈ıve algorithm tests all possible factors up to the square
√
x) and is therefore not a polynomial The Miller-Rabin algorithm runs in time proportional to
root, so it runs in O( time algorithm.
O(log3 x) but determines only probable primes.
The original AKS algorithm runs in O ̃(log12 x), and newer
versions run in O ̃(log6 x).
However, the AKS algorithm is rarely used in practice; tests using elliptic curves are much faster.
Example: Vertex Cover
Vertex Cover
Instance: a graph G and an integer k.
Problem: “There exists a subset U consisting of at most k vertices of G (called a vertex cover of G) such that each edge has at least one end belonging to U.”
Clearly, given a subset of vertices U we can determine in polynomial time whether U is a vertex cover of G with at most k elements.
So Vertex Cover is in class NP.
Example:
Instance: a propositional formula in the CNF form
C1 ∧C2 ∧…∧Cn where each clause Ci is a disjunction of propositional variables or their negations, for example
(P1 ∨¬P2 ∨P3 ∨¬P5)∧(P2 ∨P3 ∨¬P5 ∨¬P6)∧(¬P3 ∨¬P4 ∨P5)
Problem: “There exists an evaluation of the propositional variables which makes the formula true.”
Clearly, given an evaluation of the propositional variables one can determine in polynomial time whether the formula is true for such an evaluation.
So Satisfiability (SAT) is in class NP.
Example: Satisfiability
Question
Is SAT in class P?
(Partial) Answer
If each clause Ci involves exactly two variables (2SAT), then yes!
In this case, it can be solved in linear time using strongly connected components and topological sort.
Another special case of interest is when each clause involves exactly three variables (3SAT). This will be fundamental in our study of NP-complete and NP-hard problems.
P vs NP
Question
Is it the case that every problem in NP is also in P?
For example, is there a polynomial time algorithm to solve the general SAT problem?
The existence of such an algorithm would mean that finding out whether a propositional formula evaluates true in any of the 2n cases for its variables’ values is actually not much harder than simply checking one of these cases.
Intuitively, this should not be the case; determining if such a case exists should be a harder problem than simply checking a particular case.
P vs NP
However, so far no one has been able to prove (or disprove) this, despite decades of effort by very many very famous people!
The conjecture that NP is a strictly larger class of decision problems than P is known as the “P ̸= NP” hypothesis, and it is widely considered to be one of the hardest open problems in mathematics.
Table of Contents
1. Feasibility of Algorithms 2. Polynomial Reductions 3. Optimisation Problems 4. Puzzle
Polynomial Reductions
Definition
Let U and V be two decision problems. We say that U is polynomially reducible to V if and only if there exists a function f (x) such that:
1. f (x ) maps instances of U into instances of V .
2. f maps YES instances of U to YES instances of V and NO instances of U to NO instances of V, i.e. U(x) is YES if and only if V (f (x)) is YES.
3. f (x) is computable by a polynomial time algorithm.
Polynomial Reductions
false instances of U
true instances of U
x1
instances of U
false instances of V
true instances of V
f
f(x2)
f(x1)
x2
instances of V
Example: Reduction of SAT to 3SAT
Claim
Every instance of SAT is polynomially reducible to an instance of 3SAT.
Proof Outline
We introduce more propositional variables and replace every clause by a conjunction of several clauses.
Example: Reduction of SAT to 3SAT
For example, we replace the clause
P1 ∨¬P2 ∨¬P3 ∨ P4 ∨¬P5 ∨P6 (1)
with the following conjunction of “chained” 3-clauses with new propositional variables Q1, Q2, Q3:
(P1 ∨ ¬P2 ∨Q1) ∧ (¬Q1 ∨ ¬P3 ∨Q2)
∧(¬Q2 ∨ P4 ∨Q3)∧(¬Q3 ∨¬P5 ∨P6)
(2)
Easy to verify that if an evaluation of the Pi makes (1) true, then the corresponding evaluation of the Qj also makes (2) true and vice versa: every evaluation which makes (2) true also makes (1) true. Clearly, (2) can be obtained from (1) using a simple polynomial time algorithm.
Cook’s Theorem
Theorem
Every NP problem is polynomially reducible to the SAT problem.
This means that for every NP decision problem U(x) there exists a polynomial time computable function f (x) such that:
1. for every instance x of U, f (x) produces a propositional formula Φx ;
2. U(x) is true if and only if Φx is satisfiable.
NP-complete
Definition
An NP decision problem U is NP-complete (U ∈ NP-C) if every other NP problem is polynomially reducible to U.
Thus, Cook’s Theorem says that SAT is NP-complete.
NP-complete problems are in a sense universal: if we had an algorithm which solves any NP-complete problem U, then we could also solve every other NP problem as follows.
A solution of an instance x of any other NP problem V could simply be obtained by:
1. computing in polynomial time the reduction f (x) of V to U,
2. then running the algorithm that solves U on instance f(x).
Why do we care about NP-complete problems?
So NP-complete problems are the hardest NP problems – a polynomial time algorithm for solving an NP-complete problem would make every other NP problem also solvable in polynomial time.
But if P ̸= NP (as is commonly hypothesised), then there cannot be any polynomial time algorithms for solving an NP-complete problem, not even an algorithm that runs in time O(n1,000,000).
So why bother with them?
Maybe SAT is not that important – why should we care about satisfiability of propositional formulas?
Maybe NP-complete problems only have theoretical significance and no practical relevance?
Unfortunately, this could not be further from the truth!
A vast number of practically important decision problems are NP-complete!
Examples of NP-complete problems
Traveling Salesman Problem
Instance:
1. a map, i.e., a weighted directed graph with: vertices representing locations
edges representing roads between pairs of locations edge weights representing the lengths of these roads;
2. a number L.
Problem: Is there a tour along the edges which visits each location (i.e., vertex) exactly once and returns to the starting location, with total length at most L?
Think of a mailman who has to deliver mail to several addresses and then return to the post office. Can he do it while traveling less than L kilometres in total?
Examples of NP-complete problems
Register Allocation Problem
Instance:
1. an undirected unweighted graph G with: vertices representing program variables
edges representing pairs of variables which are both needed at the same step of program execution;
2. the number of registers K of the processor.
Problem: is it possible to assign variables to registers so that no edge has both vertices assigned to the same register?
In graph theoretic terms: is it possible to color the vertices of a graph G with at most K colors so that no edge has both vertices of the same color?
Examples of NP-complete problems
Vertex Cover Problem
Instance:
1. an undirected unweighted graph G with vertices and edges;
2. a number k.
Task: it it possible to choose k vertices so that every edge is incident to at least one of the chosen vertices?
Examples of NP-complete problems
Set Cover Problem
Instance:
1. a number of items n;
2. a number of bundles m such that
each bundle contains of a subset of the items each item appears in at least one bundle;
3. a number k.
Task: it it possible to choose k bundles which together contain all n items?
This problem can be extended by assigning a price to each bundle, and asking whether satisfactory bundles can be chosen within a budget b.
NP-complete problems
We will see that many other practically important problems are also NP-complete.
Be careful though: sometimes the distinction between a problem in P and a problem in NP-C can be subtle!
Examples in P vs examples in NP-C
Problems in P:
Given a graph G and two vertices s and t, is there a path from s to t of length at most K?
Given a propositional formula in CNF form such that every clause has at most two propositional variables, does the formula have a satisfying assignment? (2SAT)
Given a graph G, does G have a tour where every edge is traversed exactly once? (Euler tour)
Problems in NP-C:
Given a graph G and two vertices s and t, is there a simple path from s to t of length at least K?
Given a propositional formula in CNF form such that every clause has at most three propositional variables, does the formula have a satisfying assignment? (3SAT)
Given a graph G, does G have a tour where every vertex is visited exactly once? (Hamiltonian cycle)
Proving NP-completeness
Taking for granted that SAT is NP-complete, how do we prove NP-completeness of another NP problem?
Theorem
Let U be an NP-complete problem, and let V be another NP problem. If U is polynomially reducible to V , then V is also NP-complete.
Proof
Let g(x) be a polynomial reduction of U to V, and let W be any other NP problem.
Since U is NP-complete, there exists a polynomial reduction f(x)ofW toU.
We will now prove that g(f(x)) is a polynomial reduction of W to V.
Proving NP-completeness
false instances of W
false instances of U
false instances of V
true instances of V
g(y1)=g(f(x1))
instances of V
x1
g(f(x))
true instances of U
true instances f(x) of W
y1 g(f(x))
instances of U
g(y)
x2
instances of W
Proving NP-completeness
Proof (continued)
We first claim that g(f(x)) is a reduction of W to V.
1. Since f is a reduction of W to U, W(x) is true iff U(f(x)) is
true.
2. SincegisareductionofUtoV,U(f(x))istrueiffV(g(f(x))) is true.
Thus W(x) is true iff V(g(f(x))) is true, i.e., g(f(x)) is a reduction of W to V .
Proving NP-completeness
Proof (continued)
Since f (x) is the output of a polynomial time computable func- tion, the length |f(x)| of the output f(x) can be at most a polynomial in |x|, i.e., for some polynomial (with positive coef- ficients) P we have |f (x)| ≤ P(|x|).
Since g(y) is polynomial time computable as well, there exists a polynomial Q such that for every input y, computation of g(y) terminates after at most Q(|y|) many steps.
Thus, the computation of g(f(x)) terminates in at most: P(|x|) many steps, for the computation of f (x), plus
Q(|f (x)|) ≤ Q(P(|x|)) many steps, for the computation of g(y) (where y = f (x)).
In total, the computation of g(f(x)) terminates in at most P(|x|) + Q(P(|x|)) many steps, which is polynomial in |x|.
Proving NP-completeness
Proof (continued)
Therefore g(f(x)) is a polynomial reduction of W to V. But W could be any NP problem!
We have now proven that any NP problem is polynomially re- ducible to the NP problem V , i.e. V is NP-complete.
Example: Reducing 3SAT to VC
Task
Find a polynomial time reduction from 3SAT to Vertex Cover (VC).
If such a reduction exists, then VC is NP-complete.
Example: Reducing 3SAT to VC
Solution
Given an instance of 3SAT:
1. for each clause Ci , draw a triangle with three vertices v1i , v2i , v3i and three edges connecting these vertices;
2. for each propositional variable Pk draw a segment with vertices labeled as Pk and ¬Pk;
3. for each clause Ci connect the three corresponding vertices v1i , v2i , v3i with one end of the three segments corresponding to the variable appearing in Ci ;
if the variable appears with a negation sign, connect it with the end labeled with the negation of that letter; otherwise connect it with the end labeled with that letter.
Example: Reducing 3SAT to VC
Claim
An instance of 3SAT consisting of M clauses and N propositional variables is satisfiable if and only if the corresponding graph has a vertex cover of size at most 2M + N.
Proof
Assume there is a vertex cover with at most 2M + N vertices chosen. Then
1. each triangle must have at least two vertices chosen, and
2. each segment must have at least one of its ends chosen.
This is in total 2M + N points; thus each triangle must have exactly two vertices chosen and each segment must have exactly one of its ends chosen.
Reducing 3SAT to VC
Proof (continued)
Set each propositional letter Pi to true if Pi end of the segment corresponding to Pi is covered.
Otherwise, set a propositional letter Pi to false if ¬Pi is covered.
In a vertex cover of such a graph, every uncovered vertex of each triangle must be connected to a covered end of a segment, which guarantees that the clause corresponding to each triangle is true.
Reducing 3SAT to VC
Proof (continued)
For the reverse direction, assume that the formula has an as- signment of the variables which makes it true.
For each segment, if it corresponds to a propositional letter Pi which such a satisfying evaluation sets to true cover its Pi end.
Otherwise, if a propositional letter Pi is set to to false by the satisfying evaluation, cover its ¬Pi end.
For each triangle corresponding to a clause at least one vertex must be connected to a covered end of a segment, namely to the segment corresponding to the variable which makes that clause true; cover the remaining two vertices of the triangle.
In this way we cover exactly 2M + N vertices of the graph and clearly every edge between a segment and a triangle has at least one end covered.
Table of Contents
1. Feasibility of Algorithms 2. Polynomial Reductions 3. Optimisation Problems 4. Puzzle
NP-hard problems
Let A be a problem and suppose we have a “black box” device which for every input x instantaneously computes A(x).
We consider algorithms which are polynomial time in A. This means algorithms which run in polynomial time in the length of the input and which, besides the usual computational steps, can also use the above mentioned “black box”.
Definition
We say that a problem A is NP-hard (A ∈ NP-H) if every NP problem is polynomial time in A, i.e., if we can solve every NP problem U using a polynomial time algorithm which can also use a black box to solve any instance of A.
Note that we do NOT require that A be an NP problem; we even do not require it to be a decision problem – it can also be an optimisation problem.
An example of an NP-hard problem
Traveling Salesman Optimisation Problem
Instance:
1. a map, i.e., a weighted graph with: vertices representing locations
edges representing roads between pairs of locations edge weights representing the lengths of these roads;
Problem: find a tour along the edges which visits each location (i.e., vertex) exactly once and returns to the starting location, with minimal total length?
Think of a mailman who has to deliver mail to several addresses and then return to the post office. How can he do it while traveling the minimum total distance?
NP-hard problems
The Traveling Salesman Optimisation Problem is clearly NP-hard: using a “black box” for solving it, we can solve the Traveling Salesman Decision problem.
That is, given a weighted graph G and a number L we can determine if there is a tour containing all vertices of the graph and whose length is at most L.
We simply invoke the black box for the Traveling Salesman Optimisation Problem, which gives us the length of a shortest tour, and compare this length with L.
Since the Traveling Salesman Decision Problem is NP-complete, all other NP problems are polynomial time reducible to it.
Therefore every other NP problem is solvable using a “black box” for the Traveling Salesman Optimisation Problem.
The significance of NP-hard problems
It is important to be able to figure out if a problem at hand is NP-hard in order to know that one has to abandon trying to come up with a feasible (i.e., polynomial time) solution.
So what do we do when we encounter an NP-hard problem?
If this problem is an optimisation problem, we can try to solve it in an approximate sense by finding a solution which might not be optimal, but it is reasonably close to an optimal solution.
For example, in the case of the Traveling Salesman Optimisation Problem we might look for a tour which is at most twice the length of the shortest possible tour.
How to make progress on NP-hard problems
Thus, for a practical problem which appears to be hard, the strategy would be:
prove that the problem is indeed NP-hard, to justify not trying solving the problem exactly;
look for an approximation algorithm which provides a feasible sub-optimal solution that it is not too far from optimal.
Example: approximate Minimum Vertex Cover
Algorithm
1. Pick an arbitrary edge and cover BOTH of its ends.
2. Remove all the edges whose one end is now covered. In this way you are left only with edges which have either both ends covered or no end covered.
3. Continue picking edges with both ends uncovered until no edges are left.
Example: approximate Minimum Vertex Cover
This certainly produces a vertex cover, because edges are removed only if one of their ends is covered, and we perform this procedure until no edges are left.
The number of vertices covered is equal to twice the number of edges with both ends covered.
But the minimal vertex cover must cover at least one vertex of each such edge.
Thus we have produced a vertex cover of size at most twice the size of the minimal vertex cover.
Example: Metric Traveling Salesman Problem (MTSP)
Problem
Instance: a complete weighted graph G with weights d(i,j) of edges (to be interpreted as distances) satisfying the “triangle inequality”: for any three vertices i,j,k, we have
d (i , j ) + d (j , k ) ≥ d (i , k ).
Claim
MTSP has an approximation algorithm producing a tour of total length at most twice the length of the optimal (i.e. minimal) length tour, which we will denote by opt.
Example: Metric Traveling Salesman Problem (MTSP)
Algorithm
Find a minimum spanning tree T of G. Since the optimal tour with one of its edges e removed represents a spanning tree, we have that the total weight of T satisfies w(T) ≤ opt − w(e) ≤ opt.
If we do a depth first traversal of the tree, we will travel a total distance of 2w(T) ≤ 2opt.
Example: Metric Traveling Salesman Problem (MTSP)
We now take shortcuts to avoid visiting vertices more than once; because of the triangle inequality, this operation does not increase the length of the tour.
Approximating NP-hard optimisation problems
All NP-complete problems are equally difficult, because any of them is polynomially reducible to any other.
However, the related optimisation problems can be very different!
For example, we have seen that some of these optimisation problems allow us to get within a constant factor of the optimal answer.
Vertex Cover permits an approximation which produces a cover at most twice as large as the minimum vertex cover. Metric TSP permits an approximation which produces a tour at most twice as long as the shortest tour.
Approximating the general TSP
On the other hand, the most general Traveling Salesman Problem does not allow any approximate solution at all: if
P ̸= NP, then for no K > 1 can there be a polynomial time algorithm which for every instance produces a tour which is at most K times the length of the shortest tour!
To prove this, we show that if for some K > 0 there was indeed a polynomial time algorithm producing a tour which is at most K times the length of the shortest tour, then we could obtain a polynomial time algorithm which solves the Hamiltonian Cycle problem.
This is the problem of determining for a graph G whether G contains a cycle visiting all vertices exactly once. It is known to be NP-complete.
Approximating the general TSP
Let G be an arbitrary unweighted graph with n vertices.
We turn this graph into a complete weighted graph G∗ by setting the weights of all existing edges to 1, and then adding edges of weight K · n between the remaining pairs of vertices.
If an approximation algorithm for TSP exists, it produces a tour of all vertices with total length at most K · opt, where opt is the length of the optimal tour through G∗.
Approximating the general TSP
If the original graph G has a Hamiltonian cycle, then G∗ has a tour consisting of edges already in G and of weights equal to 1, so such a tour has length of exactly n.
Otherwise, if G does not have a Hamiltonian cycle, then the optimal tour through G∗ must contain at least one added edge of length K · n, so
opt ≥(K ·n)+(n−1)·1>K ·n.
Approximating the general TSP
Thus, our approximate TSP algorithm either returns:
a tour of length at most K · n, indicating that G has a
Hamiltonian cycle, or
a tour of length greater than K · n, indicating that G does not have a Hamiltonian cycle.
If this approximation algorithm runs in polynomial time, we now have a polynomial time decision procedure for determining whether G has a Hamiltonian cycle!
This can only be the case if P = NP.
Table of Contents
1. Feasibility of Algorithms 2. Polynomial Reductions 3. Optimisation Problems 4. Puzzle
PUZZLE!!
Problem
You are given a coin, but you are not guaranteed that it is a fair coin. It may be biased towards either heads or tails.
Use this coin to simulate a fair coin.
Hint
Try tossing the biased coin more than once!
That’s All, Folks!!