Computational complexity theory

|Computational complexity theory studies the complexity of problems amenable to algorithmic solutions, classifying them according to the amount of resources (time, workspace, ...) needed to solve an arbitrary instance of a problem.

To define complexity classes, one usually starts from a concrete machine model, for example the 1-tape deterministic Turing machine. (Deterministic) time is then the number of steps needed to compute the solution to a problem instance of a certain length. Space is the number of cells the machine needs to use, again depending on the length of the instance. It must be noted at this point that the asymptotic behaviour, or growth, independent of additive or multiplicative constants is more interesting than the actual number obtained for some machine. Complexity measures more specific to a certain machine model can also be found, such as the number of reversals (which has some surprising properties^[1]), or ink (which is consumed when overwriting a tape symbol). Also the joint restriction of space and time resources leads to useful classes.

An important distinction is between deterministic and nondeterministic computation; a nondeterministic Turing machine may "guess" how to proceed in a computation, and reject a problem instance for which a positive answer would be correct if the guesses turn out to be wrong, but never the other way round. Also, by making the right guesses it must be able to accept any instance that should be accepted.

Many central questions in computational complexity theory remain open today. Many inclusions between classes follow directly from the definition, while showing that the inclusion is proper (separating two classes, showing there are problems in the upper class that are not solvable by algorithms of lower complexity) is often inordinately hard. Some of the best-known open questions ask whether the non-deterministic and deterministic variants of certain resource-bounded computations are equally powerful.

Complexity classes may also have logical characterisations. That branch of computational complexity theory is called descriptive complexity, and is usually taught second.

1. ↑ Jianer Chen and Chee-Keng Yap: Reversal complexity, SIAM Journal on Computing, vol. 20, no. 4, pp. 622--638, SIAM 1991

• The |Complexity class article on Wikipedia
• The |Computability and Complexity wikibook
• The Complexity Zoo, providing a large list of complexity classes and links to the scientific publications establishing them