# 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.

## 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.