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 - Greedy Algorithm, Gordon Gekko, Huffman Coding

Lecture Note

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

Lecture Note

## Similar documents like this

###### POLS 001 Lecture 14: Extradition

Lecture Note

###### POLS 001 Lecture 12: Understanding Federalism

Lecture Note

###### POLS 001 Lecture Notes - Lecture 10: Fiscal Federalism, Conditionality

Lecture Note

###### POLS 001 Lecture Notes - Lecture 9: Individual And Group Rights, Equal Protection Clause

Lecture Note

###### POLS 001 Lecture 5: The Struggle for Racial Identity

Lecture Note

###### POLS 001 Lecture Notes - Lecture 4: Supremacy Clause

Lecture Note

###### POLS 001 Lecture 3: Constitutional Basis of Federalism

Lecture Note

###### POLS 001 Lecture Notes - Lecture 2: Unitary State

Lecture Note

###### BIOL 4376 Final: disperse system

Exam Note

###### BIOL 4376 Final: review

Exam Note

###### BIOL 4376 Final: 2

Exam Note

###### BIOL 4376 Final: Pharmc exam 1

Exam Note

###### BIOL 4376 Final: lecture

Exam Note

###### BIOL 4376 Study Guide - Final Guide: Coronary Artery Disease, Statin, Familial Hypercholesterolemia

Exam Note

###### BIOL 4376 Study Guide - Final Guide: Metabolic Alkalosis, Metabolic Acidosis, Hypochloremia

Exam Note