Limits of Computation Flashcards
Give an example of a well known optimisation problem?
The Travelling Salesman Problem
What problem does The Travelling Salesman Problem present?
Given a list of nodes and the distances between each of them, what is the shortest possible route that can be taken, that visits each node and returns to the start
What is the brute force method?
The brute force method involves testing out every combination
Using a brute force method, with 5 cities, how many combinations would have to be tested?
4! = 24
It’s always one less than the number of cities
What does computationally difficult mean in the context of The Travelling Salesman Problem?
- The problem is computationally difficult because it will take a long time for a fast computer to find the optimal solution.
- As the number of cities increases the problem becomes rapidly impossible to solve within a reasonable amount of time.
What are tractable problems?
- Problems that have a polynomial time solution.
- Polynomial time solutions have O(n^k)
- Problems with time complexities O(n), O(nlogn) and O(n^10) are tractable
What are intractable problems?
- Problems that don’t have a polynomial time solution.
- Problems with time complexities O(2^n) and O(n!) are intractable
- They have a theoretical solution but are very hard to solve if the n is a large value
What does intractable mean?
It means insoluble
Give an example of a tractable problem?
Dijkstra’s shortest path
What are the two options for solving an intractable problem?
- Brute force method
- Heuristic method
What is the Heuristic approach?
Finding an adequate solution by trading optimality, completeness, accuracy or precision for speed.
What are examples of using the Heuristic approach?
- The rule of thumb
- Making an educated guess
- Using common sense
What does the Halting Problem show us?
That there are some problems that cannot be solved by a computer
What is the Halting Problem?
Determines whether for a given input, a program will halt