Complexity classes

computational complexity class of decision problems solvable by a non-deterministic Turing machine in polynomial time

thumb|upright=0.8|It can be difficult to find a valid solution to a Sudoku puzzle, but once a solution has been found its validity can be verified easily. It is NP-complete to determine whether an Sudoku has a valid solution.

computational complexity class of problems

alt=Euler diagram for P, NP, NP-complete, and NP-hard set of problems.|thumb|300px|Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete). In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from L to H. That is, assuming a solution for H takes 1 unit

set of problems in computational complexity theory of related resource-based complexity

thumb|Inclusions of complexity classes including P (complexity)|P, NP, [[co-NP, BPP, P/poly, PH, and PSPACE]]

complexity class

In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

complexity class (logarithmic space)

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

hierarchy of complexity classes between P and PSPACE

complexity class

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

complexity class

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem).

In computational complexity theory, '''''' is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^{p(n)}) space, where p(n) is a polynomial function of n. Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class . If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem.

Wikimedia list article

hierarchy which classifies certain sets based on the complexity of formulas that define them

Term in Complexity Theory

In computational complexity theory, the complexity class 'NTIME(f(n))' is the set of decision problems that can be solved by a non-deterministic Turing machine that runs in time O(f(n)), where O is the big O notation, f is some function, and n is the size of the input (for which the problem is to be decided).

In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^{n^{O(1).

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE.

In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly.

complexity class

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm.

complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input

complexity class

set of all total computable functions

thumbnail|Diagram of an AC0 circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a constant.

complexity class of primitive recursive functions

class of all decision problems

complexity class, algebra

The #P-complete problems (pronounced "sharp P complete", "number P complete", or "hash P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial-time non-deterministic Turing machine.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer.

In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.

complexity class of problems solvable by a deterministic Turing machine in polynomial time and polylogarithmic space

complexity class

complexity class

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. '''Ladner's theorem''', shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

In computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It must be defined on a random-access Turing machine, since otherwise the input tape is longer than the range of cells that can be accessed by the machine. It is a very weak model of time complexity: no random-access Turing machine with a smaller deterministic time bound can access the whole input.

complexity class of problems log-space reducible to USTCON

In computational complexity theory, P/poly is a complexity class that can be defined in both circuit complexity and non-uniform complexity. Since the two definitions are equivalent, this concept bridges the two areas.

In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP.

In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP, sometimes also written 2EXPTIME) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n.

computational complexity class

In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is closed under complementation. It is situated between NL and AC1, in the sense that it contains the former and is contained in the latter. Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs: evaluating acyclic Boolean conjunctive queries checking the existence of a homomorphism between two acyclic relational structures checking the existence of solutio

property of computational problems that is a special case of NP-completeness

In computational complexity theory, the complexity class TFNP is the class of total function problems that can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial".