List of complexity classes

From Esolang
Jump to navigation Jump to search

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:

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:

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.