List of complexity classes

This summary of wikipedia:computational complexity theory is meant to give an introduction to wikipedia:complexity classes for programming language theorists and designers. We give a brief overview of complexity classes one may encounter here on this wiki.

Classes are listed roughly in order of computational power, but they are not each strictly contained in one another!

L

The complexity class L, short for LOGSPACE, contains problems which are solvable in O(log n) space. L may be thought of as a special case of P where each problem can be summarized quickly. Operationally, L may also be thought of as the subclass of P where a solution can be computed using only a constant number of pointers to the input and a logarithmic number of fixed-width counters.

Example problems in L include this listing from Cook & McKenzie 1986:

• s,t-disjoint-cycle accessibility: Does a pointwise wikipedia:permutation have both points s and t in a single orbit?
• Single-cycle permutation: Does a pointwise permutation have only one orbit?
• s,t-forest accessibility: Does a graph have a (directed) path from vertex s to vertex t?
• wikipedia:breadth-first search and wikipedia:depth-first search: Does a rooted tree have any leaves with an arbitrary L-complete property?
• wikipedia:cycle detection: Does a graph have a (directed) cycle?

And these problems in FL, the function-problem analogue of L:

• disjoint-cycle representation: What are the orbits of a pointwise permutation?
• permutation product: What is the product of two permutations, pointwise or as orbits?
• permutation powering: What is the non-negative exponent of a permutation, pointwise or as orbits?
• breadth-first search and depth-first search: Which is the first leaf in a rooted tree to have an arbitrary L-complete property?

P

The most important complexity class is P, also known as PTIME. Problems in P are solvable by deterministic classical algorithms in O(n**k) time for some positive exponent k. By letting k vary, P is self-low, which means that composition of problems in P is also in P. It is important to keep in mind that subclasses of P are not necessarily self-low; composition of two linear algorithms in the wrong way can create an accidentally quadratic algorithm.

P is formulated as a class of wikipedia:decision problems, which can only return a Boolean value. However, we often want to deal with wikipedia:function problems, which input and output the same sort of data. In this case, the relevant complexity class is called FP. This is usually a minor technical detail, but cannot be forgotten entirely. Problems in P can be transported to problems in FP and vice versa; see the other wiki for details.

An important subclass of P contains wikipedia:matrix multiplication. The wikipedia:computational complexity of matrix multiplication is not yet known, but it is below O(n³). Whatever it may be, several common algorithms have the same complexity:

• Parsing an input with a wikipedia:context-free grammar, by the wikipedia:CYK algorithm
• Evaluating a push-down automaton
• Computing the wikipedia:transitive reduction of a directed graph

Algorithms for elements of P are sometimes called "efficient". This is due to a folklore phenomenon where the exponent k tends to be small in practice and to shrink over time. However, k need not be tractably small. Matrix multiplication is one example, due to Valiant's algorithm. Another example is the wikipedia:AKS primality test, where the proof that primality testing was in P was followed by further speedups.

NP

The complexity class NP, short for NPTIME, consists of problems which are "non-deterministically" decidable in polynomial time. There are several equivalent ways to imagine NP; here is one. NP is like P, but a program is allowed to access a polynomial number of random bits, with the property that if there is a solution to the given problem, then the random bits will always yield values which lead to a solution.

There are many important facts about NP. One important and simple fact is that P is contained in NP, which is contained in PSPACE. It is believed that one of these containments is strict, but we don't know which. Figuring this out is known as the wikipedia:P versus NP problem.

Another important fact about NP is that many problems have been proven NP-complete, or complete for NP. A problem is complete for a complexity class when any other problem in the class can be reduced to it.

PSPACE

The complexity class PSPACE consists of problems which require polynomial amounts of memory to compute. Many "memory-hard" algorithms are in PSPACE. Board games like chess are in PSPACE when they have a bounded number of moves. There is a wikipedia:list of PSPACE-complete problems.

EXP

The complexity class EXP, short for EXPTIME, consists of problems which are solvable in exponential time. The most important problem in EXP is whether a given NP problem has any solutions; given a problem in NP, there are only exponentially many random values that it can access, and so there are only exponentially many different possibilities, which each take polynomial time to check.

Similarly, PSPACE is contained in EXP, because there are only exponentially many configurations for a polynomial amount of space.

R

The second-most-important complexity class is R. Problems in R are, equivalently:

• Decideable by Turing machines
• Membership predicates for recursive languages
• Computable

Similarly, the function-problem analogue of R is usually not discussed as such, but contains the total computable functions. The wikipedia:Church–Turing thesis says that this is the ceiling of computability.