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.

**Unlock Document**

###### Document Summary

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. 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.

## More from OC17497

###### Assignment #3 This is the third assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Dynamic Programming, Richard E. Bellman, Artery Recordings

Lecture Note

###### CS341 Lecture Notes - Greedy Algorithm, Gordon Gekko, Huffman Coding

Lecture Note

## Similar documents like this

###### Assignment #3 This is the third assignment from winter 2010 term

Lecture Note

###### Assignment #5 This is the fifth assignment from winter 2010 term

Lecture Note

###### Assignment #4 This is the forth assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Biconnected Component, Two Trees Of Valinor, Computer Network

Lecture Note

###### CS341 Lecture Notes - Intel 80386, Precautionary Statement, Quicksort

Lecture Note

###### CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine

Lecture Note

###### Assignment #1 This is the first assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Greedy Algorithm, Gordon Gekko, Huffman Coding

Lecture Note

###### CS341 Lecture Notes - Dynamic Programming, Richard E. Bellman, Artery Recordings

Lecture Note

###### CS341 Lecture Notes - Merge Sort, Binary Search Algorithm, Dont

Lecture Note

###### CS341 Lecture Notes - Merge Sort, Quicksort, Binary Search Algorithm

Lecture Note

###### CS341 Lecture Notes - Induced Subgraph, Adjacency Matrix, Tree Traversal

Lecture Note

###### Assignment #2 This is the second assignment from winter 2010 term

Lecture Note

###### CS341 Lecture Notes - Np-Completeness, Np-Hardness, Polynomial

Lecture Note

###### CS 341 Chapter -: exercise5

Textbook Note