Section 8 Chapter 49 - Limitations of Computation Flashcards
Tractable problem
A problem that can be solved in polynomial time or better
Intractable problem
A problem that does not have a polynomial time solution.
How to solve an intractable problem (2)
- Brute force
- Heuristic
Brute force
Testing every possible solution
Heuristic
An approach that may not provide the optimal solution, but will be far quicker than finding the optimal solution
Are all problems computable
nope
Limits on computation (2)
- Algorithmic complexity
- Hardware
The Halting Problem
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
Significance of the halting problem
Demonstrates that there are some problems that cannot be solved by a computer