Complexity class
A Complexity class is a concept from theoretical computer science and mathematics: All problems that have the same complexity are in the same complexity class. This means, that for a given input, they need about the same amount of resources, such as compute time, or memory. The most often used models for complexity are time complexity, which measures the time needed to calculate a result, or space complexity, which looks at the amount of memory or storage needed. When talking about complexity classes, a worst case scenario is usually assumed.
Complexity Class Media
A representation of the relationships between several important complexity classes
A decision problem has only two possible outputs, yes or no (alternatively, 1 or 0) on any input.
An illustration of a Turing machine. The "B" indicates the blank symbol.
A comparison of deterministic and nondeterministic computation. If any branch on the nondeterministic computation accepts then the NTM accepts.
The relationships between the fundamental probabilistic complexity classes. BQP is a probabilistic quantum complexity class and is described in the quantum computing section.
General representation of an interactive proof protocol
- solidLine
-
- solidLine
-
- solidLine
.svg)
