Class Notes (1,100,000)
CA (650,000)
UW (20,000)
CS (1,000)
CS341 (20)
Lecture

# CS341 Lecture Notes - Nsw Trainlink V Set, Correspondence Problem, Natural Number

Department
Computer Science
Course Code
CS341
Professor
Forbes Burkowski

Page:
of 20 1
Beyond NP
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.
– Examples:
The Towers of Hanoi problem.
Chess: The game tree for chess grows exponentially.
Non-computability
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.
2
• Non-computability:
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
problem instance.
There is no such algorithm.
We do not prove this: we just make some observations.
3
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
infinitum.
There is no way to bound the time of this computation
and so the problem is undecidable (in finite time).
Non-computability
• Definition:
A problem that has no algorithm for its solution is
termed non-computable.
If the non-computable problem is a decision
problem we use a more narrow term: we say it is
undecidable.