Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 
New! Save your stuff! » Create account

Complexity class

+ Save concept Saved concepts

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. [1]

75 relations: Abstract machine, AC (complexity), Algorithm, ALL (complexity), Arthur–Merlin protocol, Big O notation, Blum axioms, Boolean circuit, BPP (complexity), BQP, Circuit complexity, Co-NP, Cobham's thesis, Complete (complexity), Computability theory, Computational complexity theory, Computational model, Computational problem, Computational resource, Context-free grammar, Context-sensitive grammar, Counting problem (complexity), David S. Johnson, Decision problem, Descriptive complexity theory, DSPACE, DTIME, EXPSPACE, EXPTIME, FP (complexity), Function problem, Interactive proof system, IP (complexity), L (complexity), List of complexity classes, List of undecidable problems, Log-space reduction, Logarithm, Logical conjunction, Logical connective, Logical disjunction, Mathematical logic, Michael Garey, NC (complexity), Negation, Neil Immerman, NEXPTIME, NL (complexity), Non-deterministic Turing machine, NP (complexity), ..., NP-completeness, NP-hardness, NSPACE, NTIME, Optimization problem, P (complexity), Polynomial, Polynomial-time reduction, Probabilistic Turing machine, Promise problem, PSPACE, QMA, Quantum Turing machine, Recursive language, Recursively enumerable language, Regular grammar, RP (complexity), Savitch's theorem, Sharp-P, Space hierarchy theorem, Subset, Time complexity, Time hierarchy theorem, Turing machine, ZPP (complexity). Expand index (25 more) »

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.

New!!: Complexity class and Abstract machine · See more »

AC (complexity)

In circuit complexity, AC is a complexity class hierarchy.

New!!: Complexity class and AC (complexity) · See more »

Algorithm

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed.

New!!: Complexity class and Algorithm · See more »

ALL (complexity)

In computability and complexity theory, ALL is the class of all decision problems.

New!!: Complexity class and ALL (complexity) · See more »

Arthur–Merlin protocol

In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too).

New!!: Complexity class and Arthur–Merlin protocol · See more »

Big O notation

In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.

New!!: Complexity class and Big O notation · See more »

Blum axioms

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions.

New!!: Complexity class and Blum axioms · See more »

Boolean circuit

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.

New!!: Complexity class and Boolean circuit · See more »

BPP (complexity)

In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances.

New!!: Complexity class and BPP (complexity) · See more »

BQP

In computational complexity theory, BQP (bounded error quantum polynomial time) is 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.

New!!: Complexity class and BQP · See more »

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them.

New!!: Complexity class and Circuit complexity · See more »

Co-NP

In computational complexity theory, co-NP is a complexity class.

New!!: Complexity class and Co-NP · See more »

Cobham's thesis

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solution in time O(nc), where c is a constant that depends on the problem but not the particular instance of the problem.

New!!: Complexity class and Cobham's thesis · See more »

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") problems in the complexity class.

New!!: Complexity class and Complete (complexity) · See more »

Computability theory

Computability theory, also called recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

New!!: Complexity class and Computability theory · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Complexity class and Computational complexity theory · See more »

Computational model

A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation.

New!!: Complexity class and Computational model · See more »

Computational problem

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

New!!: Complexity class and Computational problem · See more »

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

New!!: Complexity class and Computational resource · See more »

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty).

New!!: Complexity class and Context-free grammar · See more »

Context-sensitive grammar

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols.

New!!: Complexity class and Context-sensitive grammar · See more »

Counting problem (complexity)

In computational complexity theory and computability theory, a counting problem is a type of computational problem.

New!!: Complexity class and Counting problem (complexity) · See more »

David S. Johnson

David Stifler Johnson (born December 9, 1945, Washington, D.C.) is an American computer scientist specializing in algorithms and optimization.

New!!: Complexity class and David S. Johnson · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.

New!!: Complexity class and Decision problem · See more »

Descriptive complexity theory

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

New!!: Complexity class and Descriptive complexity theory · See more »

DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine.

New!!: Complexity class and DSPACE · See more »

DTIME

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine.

New!!: Complexity class and DTIME · See more »

EXPSPACE

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(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 ESPACE.) If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.

New!!: Complexity class and EXPSPACE · See more »

EXPTIME

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.

New!!: Complexity class and EXPTIME · See more »

FP (complexity)

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 speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.

New!!: Complexity class and FP (complexity) · See more »

Function problem

In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO.

New!!: Complexity class and Function problem · See more »

Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.

New!!: Complexity class and Interactive proof system · See more »

IP (complexity)

In computational complexity theory, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system.

New!!: Complexity class and IP (complexity) · See more »

L (complexity)

In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of memory space.

New!!: Complexity class and L (complexity) · See more »

List of complexity classes

This is a list of complexity classes in computational complexity theory.

New!!: Complexity class and List of complexity classes · See more »

List of undecidable problems

In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is any possible program would sometimes give the wrong answer or run forever without giving any answer.

New!!: Complexity class and List of undecidable problems · See more »

Log-space reduction

In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.

New!!: Complexity class and Log-space reduction · See more »

Logarithm

In mathematics, the logarithm is the inverse operation to exponentiation.

New!!: Complexity class and Logarithm · See more »

Logical conjunction

In logic and mathematics, and is the truth-functional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true.

New!!: Complexity class and Logical conjunction · See more »

Logical connective

In logic, a logical connective (also called a logical operator) is a symbol or word used to connect two or more sentences (of either a formal or a natural language) in a grammatically valid way, such that the sense of the compound sentence produced depends only on the original sentences.

New!!: Complexity class and Logical connective · See more »

Logical disjunction

In logic and mathematics, or is the truth-functional operator of (inclusive) disjunction, also known as alternation; the or of a set of operands is true if and only if one or more of its operands is true.

New!!: Complexity class and Logical disjunction · See more »

Mathematical logic

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.

New!!: Complexity class and Mathematical logic · See more »

Michael Garey

Michael Randolph Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractability: A Guide to the Theory of NP-completeness.

New!!: Complexity class and Michael Garey · See more »

NC (complexity)

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.

New!!: Complexity class and NC (complexity) · See more »

Negation

In logic, negation, also called logical complement, is an operation that takes a proposition p to another proposition "not p", written ¬p, which is interpreted intuitively as being true when p is false and false when p is true.

New!!: Complexity class and Negation · See more »

Neil Immerman

Neil Immerman (24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.

New!!: Complexity class and Neil Immerman · See more »

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 2n O(1) and unlimited space.

New!!: Complexity class and NEXPTIME · See more »

NL (complexity)

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.

New!!: Complexity class and NL (complexity) · See more »

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

New!!: Complexity class and Non-deterministic Turing machine · See more »

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.

New!!: Complexity class and NP (complexity) · See more »

NP-completeness

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.

New!!: Complexity class and NP-completeness · See more »

NP-hardness

NP-hardness (''n''on-deterministic ''p''olynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP".

New!!: Complexity class and NP-hardness · See more »

NSPACE

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

New!!: Complexity class and NSPACE · See more »

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 which runs in time O(f(n)).

New!!: Complexity class and NTIME · See more »

Optimization problem

In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions.

New!!: Complexity class and Optimization problem · See more »

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes.

New!!: Complexity class and P (complexity) · See more »

Polynomial

In mathematics, a polynomial is an expression consisting of variables (or indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents.

New!!: Complexity class and Polynomial · See more »

Polynomial-time reduction

In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine.

New!!: Complexity class and Polynomial-time reduction · See more »

Probabilistic Turing machine

In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution.

New!!: Complexity class and Probabilistic Turing machine · See more »

Promise problem

In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs.

New!!: Complexity class and Promise problem · See more »

PSPACE

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

New!!: Complexity class and PSPACE · See more »

QMA

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic complexity class NP or the probabilistic complexity class MA.

New!!: Complexity class and QMA · See more »

Quantum Turing machine

A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer.

New!!: Complexity class and Quantum Turing machine · See more »

Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

New!!: Complexity class and Recursive language · See more »

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

New!!: Complexity class and Recursively enumerable language · See more »

Regular grammar

In theoretical computer science and formal language theory, a regular grammar is a formal grammar that is right-regular or left-regular.

New!!: Complexity class and Regular grammar · See more »

RP (complexity)

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

New!!: Complexity class and RP (complexity) · See more »

Savitch's theorem

In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity.

New!!: Complexity class and Savitch's theorem · See more »

Sharp-P

In computational complexity theory, the complexity class #P (pronounced "number P" or, sometimes "sharp P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP.

New!!: Complexity class and Sharp-P · See more »

Space hierarchy theorem

In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions.

New!!: Complexity class and Space hierarchy theorem · See more »

Subset

In mathematics, especially in set theory, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

New!!: Complexity class and Subset · See more »

Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

New!!: Complexity class and Time complexity · See more »

Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.

New!!: Complexity class and Time hierarchy theorem · See more »

Turing machine

A Turing machine is an abstract "machine" that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device.

New!!: Complexity class and Turing machine · See more »

ZPP (complexity)

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.

New!!: Complexity class and ZPP (complexity) · See more »

Redirects here:

Canonical complexity class, Complexity classes, Computational complexity classes, Time-complexity class.

References

[1] https://en.wikipedia.org/wiki/Complexity_class

OutgoingIncoming
Hey! We are on Facebook now! »