Round 10: Computationally more difficult problems¶
Material:
These notes
Chapter 34 in Introduction to Algorithms, 3rd ed. (online via Aalto lib) on the abstraction level of these notes:
the formal language definitions are not required,
nor are the proofs that are not in the notes.
So far almost all of our algorithms have been rather efficient,
having worst-case running times such as
Example
There is no algorithm that always decides whether a multivariate polynomial has integer-valued roots.
As a curiosity, the output to
This round
gives a semi-formal description for one important class of computationally hard but still solvable problems, called
-complete problems, andNP provides some methods for attacking such problems in practise.
Definitions by using formal languages etc and most of the proofs are not covered, they are discussed more in the Aalto courses
CS-C2150 Theoretical Computer Science, and
CS-E4530 Computational Complexity Theory.
Computational problems¶
A computational problem consists of a description of what the possible inputs, called instances of the problem, are and what is the question that should be answered on such inputs. As an example, the problem of testing whether an integer is a prime number can be expressed as the following computational problem.
Definition:
Instance: A positive integer
Question: Is
To solve this problem, one has to develop an algorithm that gives the correct answer for all possible input instances.
A problem is decidable (or “computable”, or sometimes “recursive” due to historical reasons)
if there is an algorithm that can, for all possible instances,
answer the question.
For instance, the
In a decision problem the answer is either “no” or “yes”.
Definition: The
Instance: A set
Question: Does
In a function problem the answer is either
“no” when there is no solution, and
a solution when at least one exists.
Definition: The
Instance: A set
Question: Give a subset
Mathematically, a computational problem with a no/yes answer can be defined as the set of input strings for which the answer is “yes”. Problems with a more complex answers can be defined as (partial) functions. These formal aspects will be studied more in the Aalto course “CS-C2150 Theoretical computer science”.
In optimization problems one has to find an/the optimal solution.
Definition:
Instance: A connected edge-weighted and undirected graph
Question: Give a minimum spanning tree of the graph.
For an optimization problem there usually is a corresponding decision problem with some threshold value for the solution (is there an “at least this good solution”?).
Definition:
Instance: A connected edge-weighted and undirected graph
Question: Does the graph have a spanning tree of weight
The full optimization problem is at least as hard as this decision version because an optimal solution gives immediately the solution for the decision version as well.
In computational complexity theory, the set of decidable problems can be divided in many smaller complexity classes:
— problems that can be solved in polynomial time (P always efficiently) with algorithms≈
— problems whose solution can be verified in polynomial time (or that can solved with non-deterministic machines in polynomial time)NP
— problems that can be solved with a polynomial amount of extra space (possibly in exponential time)PSPACE
— problems that can be solved in exponential timeEXPTIME and many more…
Polynomial-time solvable problems¶
A problem is polynomial-time solvable if
there is an algorithm that solves the problem in time
Note
Polynomial-time algorithms involve algorithms with running
times such as
Based on the sorting algorithms round, we know how to sort an
array of
Definition:
Instance: A sequence of integers.
Question: What is the median of the values in the sequence (“no” if the sequence is empty)?
… and the following decision version is in the class
Definition:
Instance: A sequence of integers and an integer
Question: Is the median of the values in the sequence
From the graph rounds we know how to efficiently compute
shortest paths between the vertices in a graph.
Thus the following problem belongs to
Definition:
Instance: an undirected graph
Question: Is there a path of length
However, for the longest path problem we do not know any polynomial-time algorithms:
Definition:
Instance: an undirected graph
Question: Is there a simple path of length
Similarly, we know how to compute minimum spanning trees efficiently
and the following problem is thus in
Definition:
Instance: A connected edge-weighted and undirected graph
Question: Does the graph have a spanning tree of weight
But when not all the vertices have to be included in the tree, we do not know any algorithm that would solve all the instances efficiently:
Definition:
Instance: A connected edge-weighted and undirected graph
Question: Does the graph have a tree that spans all the vertices in
Problems in NP (Non-deterministic Polynomial time)¶
There are two (and even more) equivalent ways to characterize
the decision problems in the class
Problems that can be solved in polynomial time with non-deterministic (Turing) machines.
Such non-deterministic machines can compute the same functions as our current CPUs in polynomial time. In addition, they can “branch” their computations into many “simultaneous” computations and return a solution if at least one of the branches finds a solution. They cannot be implemented with the current hardware but are rather a conceptual tool; more on non-determinism in the CS-C2150 TCS course.
Problems for which the solutions (when they exist) are
reasonably small (i.e., of polynomial size w.r.t. the input), and
easy to check (i.e., in polynomial time w.r.t. the input).
However, the solutions are not necessarily easy to find (or to prove non-existent)!
We use the latter definition and call such a small, easy-to-check solution a certificate for the instance in question. Obviously, only the “yes” instances have certificates.
The subset-sum problem¶
As a first example, consider the
Definition:
Instance: A set
Question: Does
For each instance
Example
A certificate for the instance
andS={2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993}
t=138457
is
The instance
Propositional satisfiability¶
Propositional formulas are built on
Boolean variables, and
connectives of unary negation
, binary disjunction¬ and binary conjunction∨ .∧
In Scala terms, the negation !
,
the conjunction &&
,
and
the disjunction ||
.
The difference is that in Scala, a Boolean variable always has a value
(either true of false).
Therefore, in Scala a Boolean expression (a && !b) || (!a && b)
can be evaluated at any time point to some value.
In the propositional formula level, a variable is like an unknown variable
in mathematics: it does not have a value unless we associate one by some
mapping etc.
Thus the propositional formula
Example
The formula
The formula
Definition:
Instance: a propositional formula
Question: is the formula
The propositional satisfiability problem can be understood
as the problem of deciding whether an equation
its size is linear in the number of variables in the formula, and
evaluating the formula to check whether the result is
is easy.true
To simplify theory and practice, one often uses certain normal forms of formulas:
A literal is a variable
or its negationxi ¬xi A clause is a disjunction
of literals(l1∨…∨lk) A formula is in 3-CNF (CNF means conjunctive normal form) if it is a conjunction of clauses and each clause has 3 literals over distinct variables. For instance,
is in 3-CNF.(x1∨¬x2∨x4)∧(¬x1∨¬x2∨x3)∧(x2∨¬x3∨x4)
Definition:
Instance: a propositional formula in 3-CNF.
Question: is the formula satisfiable?
Some other problems in NP¶
Definition:
Instance: An edge-weighted undirected graph
Question: Does the graph have a simple cycle visiting all the vertices and having weight
Definition:
Instance: An
Question: Can the Sudoku grid be completed?
Definition:
Instance: an undirected graph
Question: Is there a simple path of length
Definition:
Instance: A connected edge-weighted and undirected graph
Question: Does the graph have a spanning tree of weight
Definition:
Instance: A connected edge-weighted and undirected graph
Question: Does the graph have a tree that spans all the vertices in
And hundreds of others…
P versus NP¶
For polynomial-time solvable problems,
the instance itself can act as the certificate because we can always compute,
in polynomial time,
the correct no/yes answer from the instance itself.
Therefore,
NP-complete problems¶
The class
Definition: Polynomial-time computable reduction
A polynomial-time computable reduction from
a decision problem
can be computed in polynomial-time, andR(x)
is a “yes” instance ofx if and only ifB is a “yes” instance ofR(x) .A
Therefore, if we have
a polynomial time reduction from
toB , andA a polynomial-time algorithm solving
,A
then we have a polynomial-time algorithm for solving
Definition: NP-completeness
A problem
Therefore,
if an
-complete problemNP can be solved in polynomial time, then all the problems inA can, and thusNP
-complete problems are, in a sense, the most difficult ones inNP .NP
We do not know whether
The Cook-Levin Theorem¶
The fact that
Theorem: Cook 1971, Levin 1973
Soon after this, Karp [1972] then listed the next 21
Garey and Johnson, 1979: Computers and Intractability: A Guide to the Theory of NP-Completeness, or
How to prove a new problem NP-complete?¶
Suppose that we are given a new problem
show that it is in
,NP take any existing
-complete problemNP , andA reduce
to the new problemA .C
Because polynomial-time reductions compose,
the existence of the reduction
first reducing the instance
ofx to an instanceB ofR(x) (such a reductionA exists becauseR isA -complete), andNP then reducing the instance
to the instanceR(x) ofS(R(x)) . The instanceC is a “yes” instance ofx if and only ifB is a “yes” instance ofS(R(x)) .C
As a consequence,
if the new problem
Usually, but not always, the first step of showing that the new problem
is in
Proving NP-completeness: an example¶
Consider the following problem:
Definition:
INSTANCE: A social network of students and a positive integer
QUESTION: is it possible to recruit
Example
Consider the instance with the network drawn below and
This instance is indeed a “yes” instance, the green vertices below show a solution. Is the solution the only one or are there others?
This problem is in fact equivalent to a well-known graph problem called
Definition:
INSTANCE: An undirected graph
QUESTION: Is there an independent set
The
Theorem
Proof sketch
We reduce from the
For each clause
, the graph contains the verticesCi=(li,1∨li,2∨li,3) ,vi,1 , andvi,2 . Intuitively, the vertexvi,3 corresponds to the literalvi,p (eitherli,p orx for some variable¬x ) of the clause.x There is an edge between two vertices
andvi,p if and only if eithervj,q
, meaning that the vertices correspond literals in the same clause, ori=j
andli,p=x (or vice versa) for some variablelj,q=¬x .x
The first edge condition above guarantees that only one of the vertices
corresponding to literals in the same clause can be selected in an independent set.
The second one guarantees that if we select a vertex corresponding to
a literal
Suppose that
On the other hand, suppose that
As a consequence:
If
is satisfiable, thenϕ has an independent set of sizeG .K If
has an independent set of sizeG , thenK is satisfiable.ϕ
is satisfiable if and only ifϕ has an independent set of sizeG .K
Because of the above theorem,
If we could solve
Example: Reduction from
Consider the 3-CNF formula
The corresponding
The formula
Conversely, from any independent set of size 3 in the graph,
we obtain a truth assignment
Example: NP-completeness of subset-sum¶
The
is satisfiable if and only if ϕ has a subset summing to Sϕ . tϕ
Therefore, if we could solve
The numbers in
andSϕ are base-10 numbers consisting oftϕ digitsn+m .ˆx1…ˆxnˆC1…ˆCm For each variable
, the setxi includes two numbers:Sϕ
with the digitvi and the digitsˆxi=1 for each clauseˆCj=1 containing the literalCj ; the other digits are 0.xi
with the digitv′i and the digitsˆxi=1 for each clauseˆCj=1 containing the literalCj ; the other digits are 0.¬xi
For each clause
, the setCj has two numbers:Sϕ
with the digitsj and the other digits 0.ˆCj=1
with the digits′j and the other digits 0.ˆCj=2
The target value
hastϕ the digit
for each variableˆxi=1 , andxi the digit
for each clauseˆCj=4 .Cj
Example
Consider the 3-CNF formula
C1=(x1∨x2∨¬x3)
C2=(x1∨¬x2∨x3)
C3=(¬x1∨x2∨x3)
C4=(¬x1∨¬x2∨¬x3)
Observe that an assignment satisfies the formula iff
it assigns an even number of
The subset
The correctness of the reduction can be argumented as follows:
Suppose that an assignment
satisfiesτ . We can build a correspondingϕ summing toS′⊆Sϕ as follows.tϕ First, for each variable
: Ifxi for a variableτ(xi)=true , then includexi invi . Otherwise, includeS′ inv′i .S′ At this point, the digit
in the sum is 1, 2, or 3.ˆCj For each clause
, include the slack variableCj ,sj or both so that the digits′j in the sum becomesˆCj .4
In the other direction, suppose that a set
sums toS′⊆Sϕ . We build a truth assignmenttϕ that satisfiesτ as follows.ϕ First note that
contains eitherS′ orvi (but not both) for each variablev′i as the digitxi inˆxi=1 .tϕ If
, letvi∈S′ , otherwise letτ(xi)=true .τ(xi)=false Now at least one literal in each clause
is true underCj because the slack variablesτ alone can only sum the digitsj up to 3 but 4 is required inˆCj .tϕ
NP-completeness: significance¶
Of course,
the question of whether
Because there are hundreds of
There is nothing wrong in trying to prove that an
-complete problem can be solved in polynomial time. The point is that without an NP -completeness proof one would be trying the same thing without knowing it! NP
That is, suppose that you have a new problem for which you should develop an algorithm that is always efficient, i.e. runs in polynomial time.
You may end up in trying really hard for very long time,
probably without success,
if the problem turns out to be
So what to do when a problem is
Develop backtracking search algorithms with efficient heuristics and pruning techniques.
Attack some special cases occurring in practise.
Develop approximation algorithms.
Apply incomplete local search methods.
Use existing tools.
Exhaustive search¶
Perhaps the simplest way to solve computationally harder problems is
to exhaustively search through all the solution candidates.
This is usually done with a backtracking search that tries to build
a solution by extending partial solutions to larger ones.
Of course,
in the worst case this takes superpolynomial,
usually exponential or worse,
time for
As an example, recall
the following simple recursive backtracking search algorithm for
the
def solve(set: Set[Int], target: Int): Option[Set[Int]] = {
def inner(s: Set[Int], t: Int): Option[Set[Int]] = {
if(t == 0) return Some(Set[Int]())
else if (s.isEmpty) return None
val e = s.head
val rest = s - e
// Search for a solution without e
val solNotIn = inner(rest, t)
if (solNotIn.nonEmpty) return solNotIn
// Search for a solution with e
val solIn = inner(rest, t - e)
if (solIn.nonEmpty) return Some(solIn.get + e)
// No solution found here, backtrack
return None
}
inner(set, target)
}
For the instance in which
The search procedure can be improved by
adding a pruning rule that detects whether
the target value is too large or too small so that
the number in the set
def solve(set: Set[Int], target: Int): Option[Set[Int]] = {
def inner(s: Set[Int], t: Int): Option[Set[Int]] = {
if(t == 0) return Some(Set[Int]())
else if (s.isEmpty) return None
else if (s.filter(_ > 0).sum < t || s.filter(_ < 0).sum > t)
// The positive (negative) number cannot add up (down) to t
return None
val e = s.head
val rest = s - e
// Search for a solution without e
val solNotIn = inner(rest, t)
if (solNotIn.nonEmpty) return solNotIn
// Search for a solution with e
val solIn = inner(rest, t - e)
if (solIn.nonEmpty) return Some(solIn.get + e)
// No solution found here, backtrack
return None
}
inner(set, target)
}
Now the call tree for the same instance as above,
Special cases¶
Sometimes we have a computationally hard problem but the instances that occur in practise are somehow restricted special cases. In such a case, it may be possible to develop an algorithm that solves such special instances efficiently. Technically, we are not solving the original problem anymore but a different problem where the instance set is a subset of the original problem instance set.
Example: subset-sum with smallish values¶
In the case of
ifhasSubset(S,t)=true ,t=0
ifhasSubset(S,t)=false andS=∅ ,t≠0
ifhasSubset(S,t)=true orhasSubset({v2,v3,…,vn},t)=true , andhasSubset({v2,v3,…,vn},t−v1)=true
otherwise.hasSubset(S,t)=false
Now, using the memoization technique with arrays,
it is easy to implement a dynamic programming algorithm
that works in time
Take an empty array
.a For each number
in turn, insert in one passx∈S
for eacha[y+x]=x for whichy is already defined, anda[y]
.a[x]=x
That is,
in a number-by-number manner,
insert all the subset sums that can be obtained either using the number alone or by adding it to any of the sums obtainable by using earlier numbers.
The value written in the element
Example
Assume that the set of numbers is
Inspecting the array, one can directly see that, for instance,
there is a subset
Is the dynamic programming algorithm above a polynomial time algorithm for the
the size of the input instance is the number of bits needed to represent the numbers, and
therefore the value of the sum
, and thus the running time as well, can be exponentially large with respect to the instance size.∑s∈S,s>0s−∑s∈S,s<0s
For instance, the numbers that were produced in our earlier
reduction from
Reducing to an another problem¶
For some
propositional satisfiability: MiniSat and others
integer linear programming (ILP): lp_solve and others
satisfiability modulo theories: Z3 and others
and many others …
Thus if one can reduce the current problem
Example: solving Sudokus with SAT¶
Let us apply the above described approach to Sudoku solving.
Our goal is to use the sophisticated CNF SAT solvers available.
Thus, given an
the Sudoku grid has a solution if and only the formula is satisfiable, and
from a satisfying assignment for
we can build a solution for the Sudoku grid.ϕ
In practise we thus want to use the following procedure:
To obtain such a CNF formula
Each entry has at least one value:
C1=⋀1≤r≤n,1≤c≤n(xr,c,1∨xr,c,2∨…∨xr,c,n) Each entry has at most one value:
C2=⋀1≤r≤n,1≤c≤n,1≤v<v′≤n(¬xr,c,v∨¬xr,c,v′) Each row has all the numbers:
C3=⋀1≤r≤n,1≤v≤n(xr,1,v∨xr,2,v∨…∨xr,n,v) Each column has all the numbers:
C4=⋀1≤c≤n,1≤v≤n(x1,c,v∨x2,c,v∨…∨xn,c,v) Each block has all the numbers:
whereC5=⋀1≤r′≤√n,1≤c′≤√n,1≤v≤n(⋁(r,c)∈Bn(r′,c′)xr,c,v) Bn(r′,c′)={(r′√n+i,c′√n+j)∣0≤i<√n,0≤j<√n} The solution respects the given cell values
:H C6=⋀(r,c,v)∈H(xr,c,v)
The resulting formula has
Example
Consider the following Sudoku grid:
The corresponding CNF formula is:
An implementation of this approach, using the Sat4j SAT solver implemented in Java, is available in the Eclipse package for the “coloring with SAT” programming exercise. Feel free to compare its performance to the Sudoku solver you implemented in the CS-A1120 Programming 2 course.
Note
This approach of describing an instance of some other problem as a satisfiability instance, or an instance of some other similar constraint satisfaction formalism, is also called constraint programming.
It is a form of declarative programming: one only declares how the solution should look like and then a constraint solver finds one (or states that none exists).
Further references¶
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach