CS341 Lecture Notes - Nsw Trainlink V Set, Correspondence Problem, Natural Number
• 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.
•Lis 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.
– We may 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 Tof tiles, determine whether it is possible to
use this set Tto tile any rectangle in the plane.
– Note: the dimensions of a specific rectangle is not part of the
• There is no such algorithm.
– We do not prove this: we just make some observations.
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 to 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