THE UNIVERSITY OF NEW SOUTH WALES
9. INTRACTABILITY
Raveen de Silva,
office: K17 202
Copyright By PowCoder代写 加微信 powcoder
Course Admin: ,
School of Computer Science and Engineering UNSW Sydney
Term 1, 2022
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
What is the length of an input?
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).
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
Consider the decision problem A(x) =“integer x is not prime”. Is A ∈ NP?
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
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.
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
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.
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.
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
instances of U
instances of V
Contrapositive
Definition
The contrapositive of the implication p =⇒ q is ¬q =⇒ ¬p.
“Students who enjoy puzzles look forward to the end of each Algorithms lecture” is logically equivalent to “Students who dread the end of each Algorithms lecture don’t enjoy puzzles”.
Instead of proving that if x is a NO instance, then f (x ) is a NO instance, we often prove the equivalent statement that if f (x ) is a YES instance, it must have been mapped from a YES instance x.
Example: Reduction of SAT to 3SAT
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)
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
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?
Why do we care about NP-complete problems?
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
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
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
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
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?
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.
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.
Polynomial Reductions
true f(x1)
true g(f(x1))
false f(x2)
false g(f(x2))
instances of W
instances of U
instances of V
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
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 .
)manysteps, whichispolynomialin|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 reducible to the NP problem V , i.e. V is NP-complete.
Example: Reducing 3SAT to VC
Prove that Vertex Cover (VC) is NP-complete by finding a polynomial time reduction from 3SAT to VC.
We will map each instance Φ of 3SAT to a corresponding instance f(Φ) = (G,k) of VC in polynomial time, and prove that:
if Φ is a YES instance of 3SAT, then f (Φ) is a YES instance of VC, and
if f (Φ) is a YES instance of VC, then Φ is a YES instance of 3SAT. Note that this uses the earlier mentioned contrapositive.
Example: Reducing 3SAT to VC
Construction
Given an instance of 3SAT:
foreachclauseCi,drawatrianglewiththreeverticesv1i,v2i,v3i and three edges connecting these vertices;
for each propositional variable Pk draw a segment with vertices la- beled as Pk and ¬Pk;
foreachclauseCi connectthethreecorrespondingverticesv1i,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
Consider the propositional formula
(P1 ∨¬P2 ∨P3)∧(¬P1 ∨P2 ∨P3)∧(¬P1 ∨P2 ∨¬P3).
The corresponding instance of Vertex Cover is:
P1 ¬P1 P2 ¬P2 P3 ¬P3
Example: Reducing 3SAT to VC
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.
Assume there is a vertex cover with at most 2M + N vertices chosen. Then
each triangle must have at least two vertices chosen, and 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)
Recall the example
(P1 ∨¬P2 ∨P3)∧(¬P1 ∨P2 ∨P3)∧(¬P1 ∨P2 ∨¬P3)
and the corresponding VC instance.
P1 ¬P1 P2 ¬P2 P3 ¬P3
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 assignment 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 satis- fying 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
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
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 opti
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com