COMP90038 Algorithms and Complexity
NP-Completeness
Olya Ohrimenko
(Slides from Harald Søndergaard)
Lecture 22
Semester 2, 2021
Algorithms and Complexity
(Sem 2, 2021) NP-Completeness © University of Melbourne 1 / 32
Concrete Complexity
We have been concerned with the analysis of algorithms’ running times (best, average, worst cases).
Our approach has been to give a bound for the asymptotic behaviour of running time, as a function of input size.
For example, the quicksort algorithm is O(n2) in the worst case, whereas mergesort is O(nlogn).
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 2 / 32
Abstract Complexity
Complexity theory instead asks:
“What is the inherent difficulty of the problem?”
How do we know when we have come up with an algorithm which is optimal (in the asymptotic sense).
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 3 / 32
A Million Dollar Question: Is P = NP?
This is one of the seven “millennium problems”: The Clay Institute’s seven most important unsolved mathematical problems.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 4 / 32
Who Wants to Be a Millionaire?
The “P versus NP” problem comes from computational complexity theory.
If you could use USD 1,000,000, solve this—and you might well get a bonus Turing Award.
Or solve any of the other millennium problems—all but one remain unsolved.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 5 / 32
Algorithmic Problems
When we talk about a problem in computer science we almost always mean a family of instances of a general problem.
An algorithm for the problem has to work for all possible instances (input).
Example: The sorting problem—an instance is a sequence of items.
Example: The graph k-colouring problem—an instance is a graph.
Example: Equation solving problems—an instance is a set of, say, linear equations.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 6 / 32
Easy and Hard Problems
A path in a graph G is simple if it visits each node of G at most once.
Consider this problem for undirected graphs G:
SPATH: Given G and two nodes a and b in G,
is there a simple path from a to b of length at most k?
And this problem:
LPATH: Given G and two nodes a and b in G,
is there a simple path from a to b of length at least k?
If you had a large graph G, which of the two problems would you rather have to solve?
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 7 / 32
Easy and Hard Problems
a
••••• •••
There are fast algorithms to solve SPATH.
Nobody knows of a fast algorithm for LPATH.
It is likely that the LPATH problem cannot be solved in polynomial time.
(But we don’t know for sure.)
•
•
••
•
• • ••
•••
• • • b
•
Algorithms and Complexity
(Sem 2, 2021)
NP-Completeness © University of Melbourne 8 / 32
Eulerian Tours
The Eulerian tour problem is this:
EUL: In a given graph, is there a path which visits each edge of the graph once, returning to the origin?
Is there a Eulerian tour of this graph?
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 9 / 32
Eulerian Tours
The Eulerian tour problem is this:
EUL: In a given graph, is there a path which visits each edge of the graph once, returning to the origin?
Is there a Eulerian tour of this graph?
13 26 45
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 9 / 32
Hamiltonian Tours
The Hamiltonian tour problem again:
HAM: In a given graph, is there a path which visits each node of the graph once, returning to the origin?
Is there a Hamiltonian tour of this graph?
13 26 45
Algorithms and Complexity (Sem 2, 2021)
NP-Completeness © University of Melbourne 10 / 32
More Problems
Try to rank these problems according to inherent difficulty:
1 SAT: Given a propositional formula φ, is φ satisfiable?
2 SUBSET-SUM: Given a set S of positive integers and a positive integer t, is there a subset of S that adds up to t?
3 3COL: Given a graph G, is it possible to colour the nodes of G using only three colours, so that no edge connects two nodes of the same colour?
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 11 / 32
Polynomial-Time Verifiability
SAT, SUBSET-SUM, 3COL, LPATH, and HAM share an interesting property.
If somebody claims to have a solution (a “yes instance”) then we can quickly test their claim.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 12 / 32
Polynomial-Time Verifiability
SAT, SUBSET-SUM, 3COL, LPATH, and HAM share an interesting property.
If somebody claims to have a solution (a “yes instance”) then we can quickly test their claim.
In other words, these problems seem hard to solve, but solutions allow for efficient verification. They are polynomial-time verifiable.
That property is shared by a very large number of interesting problems in planning, scheduling, design, information retrieval, networks, games, …
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 12 / 32
Deterministic vs. Non-deterministic algorithms
Given an instance I of a decision problem:
Stage 1: Guess an arbitrary string S as a candidate solution
Stage 2: A deterministic algorithm takes both I and S and outputs yes if S is a solution.
This non-deterministic algorithm solves a problem if it says yes for every yes instance.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 13 / 32
P and NP
P is the class of decision problems solvable in polynomial time by a deterministic algorithm.
NP is the class of problems solvable in polynomial time by a non-deterministic polynomial algorithms.
Clearly P ⊆ NP. Is P = NP?
Most computer scientists consider this computer science’s
most important open question
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 14 / 32
Problem Reduction
The main tool used for classifying problems is reducibility.
Later we will be very precise about what we mean by reduction.
For now let us just say that we use simple cases of problem reduction all the time, for example when we translate some scheduling problem to the problem of topological sorting.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 15 / 32
Two Very Similar Integer Problems
Difference constraints, DC:
Given a set of constraints of the form x − y ∈ [k1, k2], find a solution or determine that no solution exists.
Difference constraints modulo m, DCm: As DC, except variables and operations are those of modulo-m arithmetic.
We are interested in modulo-m arithmetic because that is what a computer implements (m = 232 or m = 264).
The set of constraints
x−y ∈ [10,11] y−z ∈ [7,8] x−z ∈ [1,4]
has no solution in standard arithmetic.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 16 / 32
Two Very Similar Integer Problems
Difference constraints, DC:
Given a set of constraints of the form x − y ∈ [k1, k2], find a solution or determine that no solution exists.
Difference constraints modulo m, DCm: As DC, except variables and operations are those of modulo-m arithmetic.
We are interested in modulo-m arithmetic because that is what a computer implements (m = 232 or m = 264).
The set of constraints
x−y ∈ [10,11] y−z ∈ [7,8] x−z ∈ [1,4]
has no solution in standard arithmetic.
In modulo-16 arithmetic, one solution is
x = 11 y=0 z=8
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 16 / 32
Solving Difference Constraints
We have a fast algorithm for DC. It reduces the problem to the “no-negative-cycle” problem for weighted graphs:
x
The constraints rephrased: 11
-1 4
z
x−y≤ 11 y−x ≤ −10 y−z≤8 z−y ≤ −7 x−z≤4 z−x ≤ −1
-10
y
-7
8
The Bellman-Ford algorithm can solve the latter efficiently.
Algorithms and Complexity (Sem 2, 2021)
NP-Completeness © University of Melbourne 17 / 32
Solving Modulo m Difference Constraints
How hard can it be to adapt the DC algorithm so that it works correctly in the context of machine arithmetic, that is, with modulo m arithmetic?
How long should you keep trying when you can’t find a good algorithm?
Computational complexity theory helps . . .
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 18 / 32
The Idea of Problem Reduction, Roughly
Consider problems P and Q.
Suppose we can “faithfully” translate, without too much effort, each
instance p of P into an instance q of Q.
By faithfully we mean that it should be straightforward to extract a
solution to p from a solution to q. So to solve p we just
1 translate it to q,
2 run the algorithm for Q and
3 translate the result back.
If we can find a translation, it means that P is no harder than Q.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 19 / 32
Take Two Rather Different Problems . . .
Graph 3-colouring, 3COL:
An instance is a graph; output is “yes” if and only if the graph can have its nodes coloured using just three colours, in such a way that no two connected nodes are given the same colour.
DCm:
The difference constraint problem modulom.
x11−x12 ∈[k1,k1′] . .
xi1−xi2 ∈ [ki,ki′] . .
xn1−xn2 ∈[kn,kn′]
Algorithms and Complexity (Sem 2, 2021) NP-Completeness
© University of Melbourne 20 / 32
Faithfully Translating 3COL to DCm
12
x1−x ∈ [0,2] x2−x ∈ [0,2] x3−x ∈ [0,2] x4−x ∈ [0,2]
x1−x2 ∈ [1,m−1] x1−x3 ∈ [1,m−1] x2−x3 ∈ [1,m−1] x2−x4 ∈ [1,m−1] x3−x2 ∈ [1,m−1]
⇒
34
This way the graph can be 3-coloured if and only if the set of constraints has a solution. We have reduced 3COL to DCm.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 21 / 32
So What Has that Reduction Achieved?
It made us decide to waste no more time trying to find an efficient algorithm for DCm.
Why?
Because the reduction tells us that we have been trying to solve a problem that is at least as hard as graph 3-colouring, and 3-colouring is known to be hard.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 22 / 32
A Handle on Relative Hardness: ≤P
Let us be more precise about the concept of problem reduction.
To say that the problem translation “should be done without too much effort” will just mean “must be doable in polynomial time.”
A is polynomial-time reducible to B, A ≤P B iff there is some polynomial-time computable function f , such that for all w ,
w ∈ A iff f (w) ∈ B. Theorem:IfA≤P BandB∈PthenA∈P.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 23 / 32
NP-Completeness
B is NP-hard iff every A ∈ NP is reducible to B in polynomial time.
B is NP-complete iff
1 B ∈ NP, and
2 B is NP-hard.
Let us call the class of NP-complete
problems NPC.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 24 / 32
NP-Completeness
B is NP-hard iff every A ∈ NP is reducible to B in polynomial time.
B is NP-complete iff
1 B ∈ NP, and
2 B is NP-hard.
Let us call the class of NP-complete
Our interest in this class owes a lot to this result:
Theorem: If B ∈ NPC and B ∈ P then P = NP.
problems NPC.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 24 / 32
NP-Completeness and NP-Hardness
NP-complete problems are the NP-hard problems in NP.
NP • • •
••
NP-hard problems
• •
Here arrows indicate polynomial time reduction (a transitive relation). Note: All problems in NPC stand or fall together!
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 25 / 32
NP-Complete Problems
SAT, SUBSET-SUM, 3COL, LPATH, and HAM, as well as thousands of other interesting and practically relevant problems have been shown to be NP-complete.
This explains the continuing interest in NP-completeness and related concepts from complexity theory.
For such problems we do not know of solutions that are essentially better than exhaustive search.
There are many other interesting complexity classes, including space complexity classes and probabilistic classes.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 26 / 32
Open Problems
So we don’t know whether P = NP, and there are many other unsolved problems of similar type. We know:
P ⊆ NP
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 27 / 32
Dealing with NP-Completeness
Pseudo-polynomial problems (SUBSET-SUM and KNAPSACK are in this class): Unless you have really large data, don’t worry; for reasonably-sized sets and numbers, the bad behaviour will not have kicked in yet.
Clever engineering to push the boundary slowly: SAT solvers. Approximation algorithms: Settle for less than perfection.
Live happily with intractability: Sometimes the bad instances never turn up in practice.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 28 / 32
Approximation Algorithms
For intractable optimization problems, it makes sense to look for approximation algorithms that are fast and still find solutions that are reasonably close to the optimal.
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 29 / 32
Example
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 30 / 32
Example
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 31 / 32
Summary and Next Lecture
Hard problems
P vs. NP
Sometimes we run into more trouble than mere intractability!
There are practically important computational problems that have no algorithmic solution!
Next lecture: research on data structure and algorithms in security and cryptography
Algorithms and Complexity (Sem 2, 2021) NP-Completeness © University of Melbourne 32 / 32