# Computing - Limits of Computation

> Source: https://ollybritton.com/notes/a-level/computing/topics/limits-of-computation/ · Updated: 2021-04-28 · Tags: computing, school

## See Also
- [Computing - Turing Machines](https://ollybritton.com/notes/a-level/computing/topics/turing-machines/)

## Flashcards
##### What is an insoluble problem??
A problem that is impossible to solve.

##### What are the time complexities for a tractable problem??
Polynomial time, e.g. $O(n^2)$ or $O(n^3)$

##### What is an intractable problem??
A problem where the computational demands grow so quickly that it's impossible to solve non-theoretically.

##### What sort of time complexities does an intractable problem have??
Exponential.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt