Complexity Class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:

the set of problems that can be solved by an abstract machine M using O(f(n)) of resource R, where n is the size of the input.

For example, the class NP is the set of decision problems whose solutions can be determined by a non-deterministic Turing machine in polynomial time, while the class PSPACE is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space.

The simpler complexity classes are defined by the following factors:

  • The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems (an example is FP), counting problems (e.g. #P), optimization problems, promise problems, etc.
  • The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on nondeterministic Turing machines, boolean circuits, quantum Turing machines, monotone circuits, etc.
  • The resource (or resources) that are being bounded and the bounds: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.

Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity.

Bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" (Goldreich 2008, Chapter 1.2). This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.

The Blum axioms can be used to define complexity classes without referring to a concrete computational model.

Read more about Complexity Class:  Important Complexity Classes, Reduction, Closure Properties of Classes, Relationships Between Complexity Classes

Other articles related to "complexity, complexity class, class":

Complete (complexity)
... In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive ... More formally, a problem p is called hard for a complexity class C under a given type of reduction, if there exists a reduction (of the given type) from ... If a problem is both hard for the class and a member of the class, it is complete for that class (for that type of reduction) ...
Relationships Between Complexity Classes - Hierarchy Theorems
... For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems ... Thus there are pairs of complexity classes such that one is properly included in the other ... theorems form the basis for most separation results of complexity classes ...
Natural Proof
... In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one ... Specifically, natural proofs prove lower bounds on the circuit complexity of boolean functions ... specified in their main theorem, Razborov and Rudich show that these proofs cannot separate certain complexity classes ...
Cobham's Thesis
... be computed in polynomial time that is, if they lie in the complexity class P ... earliest mentions of the concept of the complexity class P, consisting of problems decidable in polynomial time ... Cobham theorized that this complexity class was a good way to describe the set of feasibly computable problems ...
Las Vegas Algorithm - Complexity Class
... The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP ... Namely the class RP consists of all decision problems for which a randomized polynomial-time algorithm exists that always answers correctly when the correct ...

Famous quotes containing the words class and/or complexity:

    Where justice is denied, where poverty is enforced, where ignorance prevails, and where any one class is made to feel that society is in an organized conspiracy to oppress, rob, and degrade them, neither persons nor property will be safe.
    Frederick Douglass (c. 1817–1895)

    In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...
    Marcel Proust (1871–1922)