See Also
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.
Backlinks
Metadata
date: 2021-04-28 10:20
tags:
- '@?computing'
- '@?school'
- '@?public'
title: Computing - Limits of Computation