# Limits of Computation Flashcards

1
Q

Give an example of a well known optimisation problem?

A

The Travelling Salesman Problem

2
Q

What problem does The Travelling Salesman Problem present?

A

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

3
Q

What is the brute force method?

A

The brute force method involves testing out every combination

4
Q

Using a brute force method, with 5 cities, how many combinations would have to be tested?

A

4! = 24

It’s always one less than the number of cities

5
Q

What does computationally difficult mean in the context of The Travelling Salesman Problem?

A
• 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.
6
Q

What are tractable problems?

A
• 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
7
Q

What are intractable problems?

A
• 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
8
Q

What does intractable mean?

A

It means insoluble

9
Q

Give an example of a tractable problem?

A

Dijkstra’s shortest path

10
Q

What are the two options for solving an intractable problem?

A
• Brute force method

- Heuristic method

11
Q

What is the Heuristic approach?

A

Finding an adequate solution by trading optimality, completeness, accuracy or precision for speed.

12
Q

What are examples of using the Heuristic approach?

A
• The rule of thumb
• Making an educated guess
• Using common sense
13
Q

What does the Halting Problem show us?

A

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

14
Q

What is the Halting Problem?

A

Determines whether for a given input, a program will halt