Section 8 Chapter 49 - Limitations of Computation

Question 1

Tractable problem

Answer 1

A problem that can be solved in polynomial time or better

Question 2

Intractable problem

Answer 2

A problem that does not have a polynomial time solution.

Question 3

How to solve an intractable problem (2)

Answer 3

• Brute force

- Heuristic

Question 4

Brute force

Answer 4

Testing every possible solution

Question 5

Heuristic

Answer 5

An approach that may not provide the optimal solution, but will be far quicker than finding the optimal solution

Question 6

Are all problems computable

Answer 6

nope

Question 7

Limits on computation (2)

Answer 7

• Algorithmic complexity

- Hardware

Question 8

The Halting Problem

Answer 8

The halting problem is the problem of determining for a given input whether a program will finish running or continue forever. It can be proven that no program could solve the halting problem for all possible programs

Question 9

Significance of the halting problem

Answer 9

Demonstrates that there are some problems that cannot be solved by a computer