Share This
table started by
pumpkin for the Computer Science Base
There is no user-contributed description yet.
Add More Topics
Save this view to a base, or just for yourself.
54 Complexity class topics matching:
Filter this Collection| x name | x image | x Problems with this complexity | x article |
|---|---|---|---|
| x P |
In computational complexity theory, P, also known as PTIME or DTIME(n), is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of...
|
||
| x NP |
In computational complexity theory, NP is one of the most fundamental complexity classes. The abbreviation NP refers to "nondeterministic polynomial time".
Intuitively, NP is the set of all decision problems for which the 'yes'-answers have simple...
|
||
| x NP-complete |
|
Travelling salesman problem |
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, with NP standing for nondeterministic polynomial time), is a class of problems having two properties
Although any given solution to such a problem can be...
|
| 3SAT | |||
| Vertex cover problem | |||
| Dominating set problem | |||
| Domatic number | |||
| more ▼ | |||
| x Co-NP |
In computational complexity theory, co-NP is a complexity class. A problem is a member of co-NP if and only if its complement is in complexity class NP. In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of no...
|
||
| x P-complete |
In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:
Formally, a decision problem is P-complete (complete for the complexity class P) if it is in P and that every problem in P can be reduced to it by...
|
||
| x AH | |||
| x AP | |||
| x APX |
In complexity theory the class APX (an abbreviation of "approximable") is the set of NPO optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation...
|
||
| x AM | |||
| x BPP |
In complexity theory, BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. The abbreviation BPP refers to Bounded-error, Probabilistic,...
|
||
| x BQP |
In computational complexity theory BQP stands for Bounded error, Quantum, Polynomial time. It denotes the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.
In...
|
||
| x Co-NP-complete |
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P. If there exists a way to solve a co-NP-complete problem quickly,...
|
||
| x DSPACE |
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...
|
||
| x DTIME |
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...
|
||
| x E |
In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2 and is therefore equal to the complexity class DTIME(2).
E is less important to complexity...
|
||
| x ELEMENTARY |
In computational complexity theory, the complexity class ELEMENTARY is the union of the classes in the exponential hierarchy.
The name was coined by Laszlo Kalmar, in the context of recursive functions and undecidability; most problems in it are far...
|
||
| x ESPACE |
For the car, see Renault Espace
In computational complexity theory, the complexity class ESPACE is the set of decision problems that can be solved by a deterministic Turing machine in space 2.
See also EXPSPACE.
|
||
| x EXPTIME |
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2) time, where p(n) is a polynomial function of n.
In terms of DTIME,
We know...
|
||
| x EXPSPACE |
In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2) 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...
|
||
| x FNP |
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following...
|
||
| x FP |
In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P. Roughly...
|
||
| x FPNP | |||
| x FPT | |||
| x IP |
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Goldwasser, et al. in 1985. An interactive proof system consists of...
|
||
| x L |
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. Intuitively, logarithmic space is enough space to hold a...
|
||
| x LOGCFL |
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 situated between NL and AC1, in the sense that it contains the...
|
||
| x MA | |||
| x NC |
In complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c...
|
||
| x NE |
In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time O(k) for some k.
NE is less important to complexity theory than the similar class NEXPTIME...
|
||
| x NESPACE |
In computational complexity theory, the complexity class NESPACE is the set of decision problems that can be solved by a non-deterministic Turing machine in space O(2). If ESPACE is defined as the set of decision problems that can be solved by a...
|
||
| x NEXPTIME |
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 O(2) for some polynomial p(n), and unlimited space.
In...
|
||
| x NEXPSPACE |
In computational complexity theory, the complexity class NEXPSPACE is the set of decision problem that can be solved by a non-deterministic Turing machine in space O(2) for some polynomial function p(n).
In terms of NSPACE,
It is equal to...
|
||
| x NL |
In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.
NL is a...
|
||
| x NONELEMENTARY |
In computational complexity theory, the complexity class NONELEMENTARY is the complement of the class ELEMENTARY.
Example decidable problems in NONELEMENTARY this class are:
|
||
| x NP-easy |
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 other words, a problem X is NP-easy if and...
|
||
| x NP-equivalent |
In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems.
For example, the problem FIND-SUBSET-SUM is...
|
||
| x NP-hard |
NP-hard (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete...
|
||
| x NSPACE |
In computational complexity theory, the complexity class NSPACE(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using space O(f(n)), and unlimited time. It is the non-deterministic counterpart of DSPACE...
|
||
| x NTIME |
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 using time O(f(n)), and unlimited space.
The well-known complexity class NP can be defined...
|
||
| x P/poly |
In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also (equivalently) defined as the class of languages that have a...
|
||
| x PCP |
In computational complexity theory, a probabilistically checkable proof (in short PCP) is a type of proof that can be checked by a randomized verification algorithm with bounded query complexity.
The complexity class PCP is the class of decision...
|
||
| x PH |
In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:
PH was first defined by Larry Stockmeyer. It is contained in P (the class of problems that are decidable by a polynomial...
|
||
| x PNP | |||
| x PP |
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The...
|
||
| x PR |
PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function. This includes addition, multiplication, exponentiation, tetration, etc.
The Ackermann...
|
||
| x PSPACE |
|
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.
If we denote by SPACE(t(n)), the set of all problems that can be solved by Turing machines...
|
|
| x PSPACE-complete |
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time (see complete (complexity)). The problems that are PSPACE-complete can be...
|
||
| x R |
In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages. R is often identified with the class of 'effectively computable' functions (the Church-Turing thesis)....
|
||
| x RE |
In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the...
|
||
| x RP |
In complexity theory, RP ("randomized polynomial time") is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
In other words, the algorithm is allowed to flip a truly random coin while it is...
|
||
| x RL |
RL is the class of problems solvable in logarithmic space by randomized algorithms.
|
||
| x SL |
In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity), which is the problem of determining whether there exists a path between two...
|
||
| x UP |
In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. UP contains P...
|
||
| x ZPP |
In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
In other words, the algorithm is allowed to flip a truly-random coin...
|
||
