# 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