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, andprovides 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 ( always efficiently) with algorithms
— problems whose solution can be verified in polynomial time (or that can solved with non-deterministic machines in polynomial time)
— problems that can be solved with a polynomial amount of extra space (possibly in exponential time)
— problems that can be solved in exponential time 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
and
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.
To simplify theory and practice, one often uses certain normal forms of formulas:
A literal is a variable
or its negation A clause is a disjunction
of literals 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.
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, and
is a “yes” instance of if and only if is a “yes” instance of .
Therefore, if we have
a polynomial time reduction from
to , and a polynomial-time algorithm solving
,
then we have a polynomial-time algorithm for solving
Definition: NP-completeness
A problem
Therefore,
if an
-complete problem can be solved in polynomial time, then all the problems in can, and thus
-complete problems are, in a sense, the most difficult ones in .
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
,take any existing
-complete problem , andreduce
to the new problem .
Because polynomial-time reductions compose,
the existence of the reduction
first reducing the instance
of to an instance of (such a reduction exists because is -complete), and then reducing the instance
to the instance of . The instance is a “yes” instance of if and only if is a “yes” instance of .
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 vertices , , and . Intuitively, the vertex corresponds to the literal (either or for some variable ) of the clause. There is an edge between two vertices
and if and only if either
, meaning that the vertices correspond literals in the same clause, or
and (or vice versa) for some variable .
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 size . If
has an independent set of size , then is satisfiable.
is satisfiable if and only if has an independent set of size .
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 .
Therefore, if we could solve
The numbers in
and are base-10 numbers consisting of digits . For each variable
, the set includes two numbers:
with the digit and the digits for each clause containing the literal ; the other digits are 0.
with the digit and the digits for each clause containing the literal ; the other digits are 0.
For each clause
, the set has two numbers:
with the digit and the other digits 0.
with the digit and the other digits 0.
The target value
has the digit
for each variable , and the digit
for each clause .
Example
Consider the 3-CNF formula
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 to as follows. First, for each variable
: If for a variable , then include in . Otherwise, include in . At this point, the digit
in the sum is 1, 2, or 3. For each clause
, include the slack variable , or both so that the digit in the sum becomes .
In the other direction, suppose that a set
sums to . We build a truth assignment that satisfies as follows. First note that
contains either or (but not both) for each variable as the digit in . If
, let , otherwise let . Now at least one literal in each clause
is true under because the slack variables alone can only sum the digit up to 3 but 4 is required in .
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 -completeness proof one would be trying the same thing without knowing it!
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
if ,
if and ,
if or , and
otherwise.
Now, using the memoization technique with arrays,
it is easy to implement a dynamic programming algorithm
that works in time
Take an empty array
. For each number
in turn, insert in one pass
for each for which is already defined, and
.
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.
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:
Each entry has at most one value:
Each row has all the numbers:
Each column has all the numbers:
Each block has all the numbers:
where The solution respects the given cell values
:
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