Provably intractable problems:
We have seen various NP-complete problems
that take up exponential time for their solution.
But we cannot seem to prove that this is necessary.
There are other problems which are intractable
but can be proven to be intractable.
That is: there is a proof that the minimum time must be
exponential in the size of the input.
The Towers of Hanoi problem.
Chess: The game tree for chess grows exponentially.
Computation has its limits:
There are problems that cannot be solved by any
algorithm (even if exponential time is allowed).
Notions of computability:
In our discussion of computability we will utilize
some programming language L.
L is to be defined later.
We will show that there are problems for which there is
no algorithm possible, expressed in this language L.
We will also have an associated set of legal inputs
for a problem.
A proposed solution of a problem must successfully
work for all such inputs.
There are problems that can be easily stated but
no algorithm can solve them.
Note: we do not mean no efficient algorithm.
Difficulty goes beyond simply requiring exponential time.
Example: The Tiling Problem.
We are given a finite set of square tiles of the same size,
with four colours (not necessarily different) associated
with each edge.
We wish to tile a rectangular area that has edge lengths
of integer size.
The colours must match on an edge.
Rotations are not permitted.
Wemay use as many tiles of a given pattern as we wish.
For some sets of tiles it is fairly easy to see that
any size of rectangle could be properly tiled.
For other sets of tiles it is fairly easy to establish
that no such solutions exist
Statement of The Tiling Problem:
Given a set T of tiles, determine whether it is possible to
use this set T to tile any rectangle in the plane.
Note: the dimensions of a specific rectangle is not part of the
There is no such algorithm.
Wedo not prove this: we just make some observations.
2 Non-computability of Tiling
Can we solve the problem by brute force?
For some tile sets we can group tiles to make up
repeating patterns that will guarantee success for any
larger rectangle (result is TRUE).
For some tile sets we can find rectangles that cannot
be tiled (result is FALSE due to this counterexample).
But there are tiling sets with no repeating patterns
(this can be proven but it is very difficult .o do so)
In these cases, we would have to work with all tilings
for rectangles of size 1x1, 1x2, 2x2, 1x3, 2x3, 3x3 ad
There is no way to bound the time of this computation
and so the problem is undecidable (in finite time).
A problem that has no algorithm for its solution is
If the non-computable problem is a decision
problem we use a more narrow term: we say it is
3 Problems similar to the tiling problem:
Can the tiles be laid down in a domino fashion so as
to make a path from point v in the plane to another
point w in the plane?
If we restrict the path to lie in a given rectangle the problem is
decidable (exhaustive search).
If we do not restrict the path (it can wander the entire plane
before arriving at w), then again the problem is decidable.
If we restrict the path to a half infiniteplane the problem is
Word Correspondence is Undecidable
The word correspondence problem:
We are given two sequences of words:
(U 1 U 2 , U )nand (V , 1 , 2, V ) ench word
made up of symbols taken from a finite alphabet.
Can we find a sequence of words taken from the U set
and a corresponding sequence of words taken from
the V set (same indices being used) such that the
concatenation of words from the U set is the same as
the concatenation of words from the V set.
There is no algorithm that can do this for all possible U, V
The problem is undecidable.