List of complexity classes

This is a list of complexity classes that are considered in complexity theory.

Use the classes in their definitions different machine models. The main models are Turing machines; they can work deterministic, non-deterministic or probabilistic. As a complexity measure especially time complexity and space complexity are considered ( depending on the problem size and input length n ). The assessment of specific duration or memory consumption is expressed by the Landau notation.

For each class - if possible - the definition in the DTIME, DSPACE, NTIME or NSPACE notation, and a brief natural language explanation given.