Computing - Limits of Computation

Created: April 28, 2021

---

See Also

• [[Computing - Turing Machines]]^A

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.

---

Related posts

• [[Computing - Turing Machines]]^A

  (outgoing)
• [[Computing - Syllabus]]^A

  (incoming)
• [[Course - Models of Computation MT23]]^U

  (sim: 0.47)
• [[FRACTRAN and theoretically cheating at your A-levels]]^B

  (sim: 0.462)
• [[Computing - Functional Programming]]^A

  (sim: 0.441)
• [[Computing - Big Data]]^A

  (sim: 0.438)