Class Notes (835,073)
Canada (508,912)
CS 341 (26)

Lecture #10 - NoN-Computability fall 2009

20 Pages
Unlock Document

Computer Science
CS 341
Forbes Burkowski

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. 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. 1 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. 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 problem instance. 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 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. 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 undecidable! 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. The problem: 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 combinations. The problem is undecidable. 4
More Less

Related notes for CS 341

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.