SettingsComputational complexity theory
Aanderaa-Karp–Rosenberg conjecture
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex u and ver...
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex u and ver...
Aanderaa–Karp–Rosenberg conjecture
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectu...
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectu...
Advice (complexity)
In Computational complexity theory, an advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself.
In Computational complexity theory, an advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself.
Analysis of algorithms
In computer science, the analysis of algorithms is the determination of the amount of resources necessary to execute them.
In computer science, the analysis of algorithms is the determination of the amount of resources necessary to execute them.
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems.
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems.
Asymptotic computational complexity
In computational complexity theory, asymptotic computational complexity is the usage of the asymptotic analysis for the estimation of computational complexity of algorithms and computational pr...
In computational complexity theory, asymptotic computational complexity is the usage of the asymptotic analysis for the estimation of computational complexity of algorithms and computational pr...
Averaging argument
In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems.
In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems.
Best, worst and average case
In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.
In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.
Blum's speedup theorem
In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is an important theorem about the complexity of computable functions.
In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is an important theorem about the complexity of computable functions.
Boolean circuit
A Boolean circuit is a mathematical model of computation used in studying computational complexity theory.
A Boolean circuit is a mathematical model of computation used in studying computational complexity theory.
Certificate (complexity)
In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language.
In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language.
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 th...
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 th...
Circuits over sets of natural numbers
Circuits over natural numbers is a mathematical model used in studying computational complexity theory.
Circuits over natural numbers is a mathematical model used in studying computational complexity theory.
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 o...
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 o...
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects.
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects.
Combinatorial search
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects.
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects.
Communication complexity
The notion of communication complexity was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob).
The notion of communication complexity was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob).
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class.
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class.
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
Complexity index
Besides complexity intended as a difficulty to compute a function (see computational complexity), in modern computer science and in statistics another complexity index of a function stands for d...
Besides complexity intended as a difficulty to compute a function (see computational complexity), in modern computer science and in statistics another complexity index of a function stands for d...
Compression theorem
In computational complexity theory the compression theorem is an important theorem about the complexity of computable functions.
In computational complexity theory the compression theorem is an important theorem about the complexity of computable functions.
Computation tree
A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input.
A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input.
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 inh...
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 inh...
Computational resource
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
Computational topology
Algorithmic topology, or computational topology, is a subfield of topology encompassing computer science.
Algorithmic topology, or computational topology, is a subfield of topology encompassing computer science.
Computing the permanent
In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity ...
In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity ...
Configuration graph
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.
Constructible function
In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f can be constructed from n by a Turing machine in ...
In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f can be constructed from n by a Turing machine in ...
Cook-Levin theorem
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.
Cook–Levin theorem
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.
Decision tree model
In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is consider...
In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is consider...
Descriptive complexity theory
Descriptive complexity is a branch of computational complexity theory that characterizes complexity classes by the type of logic needed to express the languages in them.
Descriptive complexity is a branch of computational complexity theory that characterizes complexity classes by the type of logic needed to express the languages in them.
Dynamic problem (algorithms)
Dynamic problems in computational complexity theory are problems stated in terms of the changing input data.
Dynamic problems in computational complexity theory are problems stated in terms of the changing input data.
Effective complexity
Effective complexity is a measure of complexity defined in a 2003 paper by Murray Gell-Mann and Seth Lloyd that attempts to measure the amount of non-random information in a system.
Effective complexity is a measure of complexity defined in a 2003 paper by Murray Gell-Mann and Seth Lloyd that attempts to measure the amount of non-random information in a system.
Electronic Colloquium on Computational Complexity
The Electronic Colloquium on Computational Complexity (ECCC) is an electronic archive of research papers in computational complexity theory, a branch of computer science.
The Electronic Colloquium on Computational Complexity (ECCC) is an electronic archive of research papers in computational complexity theory, a branch of computer science.
Gadget (computer science)
In computer science and computational complexity theory, gadgets are often used to construct reductions from one problem to another.
In computer science and computational complexity theory, gadgets are often used to construct reductions from one problem to another.
Gap theorem
In computational complexity theory the Gap Theorem is a major theorem about the complexity of computable functions.
In computational complexity theory the Gap Theorem is a major theorem about the complexity of computable functions.
Generalized game
In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size.
In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size.
Generic-case complexity
Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".
Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".
Hardness of approximation
In computer science, hardness of approximation is a field that studies the complexity of finding near-optimal solutions to optimization problems.
In computer science, hardness of approximation is a field that studies the complexity of finding near-optimal solutions to optimization problems.
Information-based complexity
Information-based complexity (IBC) studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical f...
Information-based complexity (IBC) studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical f...
Integer circuit
Integer circuits is a mathematical model used in studying computational complexity theory.
Integer circuits is a mathematical model used in studying computational complexity theory.
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.
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.
Interval-valued computation
Interval-valued computation is a special kind of theoretical models for computation.
Interval-valued computation is a special kind of theoretical models for computation.
Introduction to the Theory of Computation
Introduction to the Theory of Computation (ISBN 0-534-95097-3) is a standard textbook in theoretical computer science, written by Michael Sipser.
Introduction to the Theory of Computation (ISBN 0-534-95097-3) is a standard textbook in theoretical computer science, written by Michael Sipser.
Kernelization
In computer science, a kernelization is an efficient algorithm that preprocesses instances of decision problems by mapping them to equivalent instances with a guaranteed upper bound on the size ...
In computer science, a kernelization is an efficient algorithm that preprocesses instances of decision problems by mapping them to equivalent instances with a guaranteed upper bound on the size ...
Klee–Minty cube
The Klee–Minty cube has been used to analyze the behavior of many algorithms, both in the worst case and on average.
The Klee–Minty cube has been used to analyze the behavior of many algorithms, both in the worst case and on average.
L-reduction
L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features.
L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features.
Leaf language
In computational complexity theory, a leaf language is a method of characterizing a complexity class by formalizing what it means for a machine to "accept" an input.
In computational complexity theory, a leaf language is a method of characterizing a complexity class by formalizing what it means for a machine to "accept" an input.
Linear speedup theorem
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any Turing machine solving a problem in time f(n), there is anothe...
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any Turing machine solving a problem in time f(n), there is anothe...
List decoding
In computer science, particularly in coding theory, list decoding is an alternative to unique decoding of error correcting codes for large error rates.
In computer science, particularly in coding theory, list decoding is an alternative to unique decoding of error correcting codes for large error rates.
List-decoding
In computer science, particularly in coding theory, list decoding is an alternative to unique decoding of error correcting codes for large error rates.
In computer science, particularly in coding theory, list decoding is an alternative to unique decoding of error correcting codes for large error rates.
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.
Logical depth
Logical depth is a measure of complexity devised by Charles H. Bennett based on the computational complexity of an algorithm that can recreate a given piece of information.
Logical depth is a measure of complexity devised by Charles H. Bennett based on the computational complexity of an algorithm that can recreate a given piece of information.
Low (complexity)
In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A.
In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A.
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem.
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem.
Natural proof
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one.
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one.
Nondeterministic algorithm
In computer science, a nondeterministic algorithm is an algorithm that defines multiple ways of processing the same input, without any specification of which one will be taken.
In computer science, a nondeterministic algorithm is an algorithm that defines multiple ways of processing the same input, without any specification of which one will be taken.
Padding argument
In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal.
In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal.
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect...
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect...
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomiz...
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomiz...
Pebble game
In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph.
In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph.
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time.
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time.
Proof (truth)
A proof is an argument or sufficient evidence for the truth of a proposition.
A proof is an argument or sufficient evidence for the truth of a proposition.
Proof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce.
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce.
Propositional proof system
In propositional calculus and proof complexity a propositional proof system (pps), also called a Cook–Reckhow propositional proof system, is system for proving classical propositional taut...
In propositional calculus and proof complexity a propositional proof system (pps), also called a Cook–Reckhow propositional proof system, is system for proving classical propositional taut...
Pseudo-polynomial time
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the leng...
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the leng...
Pseudorandom generator theorem
In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as...
In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as...
PTAS reduction
In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems.
In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems.
Quantum capacity
In the theory of quantum communication, the quantum capacity is the highest rate at which quantum information can be communicated over many independent uses of a noisy quantum channel from a sen...
In the theory of quantum communication, the quantum capacity is the highest rate at which quantum information can be communicated over many independent uses of a noisy quantum channel from a sen...
Quantum complexity theory
Quantum complexity theory is a part of computational complexity theory in theoretical computer science.
Quantum complexity theory is a part of computational complexity theory in theoretical computer science.
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data.
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data.
Randomness extractor
A randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source, generates a random output that is shorter, but uniformly distributed.
A randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source, generates a random output that is shorter, but uniformly distributed.
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem.
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem.
Schaefer's dichotomy theorem
In computational complexity theory, a branch of computer science, Schaefer's theorem states necessary and sufficient conditions under which a finite set S of Boolean relations yields polynom...
In computational complexity theory, a branch of computer science, Schaefer's theorem states necessary and sufficient conditions under which a finite set S of Boolean relations yields polynom...
Semi-membership
In mathematics and theoretical computer science, the semi-membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set; a...
In mathematics and theoretical computer science, the semi-membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set; a...
SO (complexity)
SO is equal to PH, more precisely we have that formula in prenex normal form where existential and universal of second order alternate k times are the kth level of the polynomial hierarchy.
SO is equal to PH, more precisely we have that formula in prenex normal form where existential and universal of second order alternate k times are the kth level of the polynomial hierarchy.
Sparse language
In computational complexity theory, a sparse language is a formal language (a set of strings) such that the number of strings of length n in the language is bounded by a polynomial function ...
In computational complexity theory, a sparse language is a formal language (a set of strings) such that the number of strings of length n in the language is bounded by a polynomial function ...
Speedup theorem
In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same p...
In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same p...
Strongly NP-complete
In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness.
In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness.
Switching lemma
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.
The Complexity of Songs
"The Complexity of Songs" was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory.
"The Complexity of Songs" was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory.
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 size of the input to the problem.
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 size of the input to the problem.
Transcomputational problem
In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.
In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.
Transdichotomous model
The transdichotomous model is a computational model where the problem size matches the machine word size.
The transdichotomous model is a computational model where the problem size matches the machine word size.
Truth-table reduction
In computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.
In computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.
Turing reduction
In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known.
In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known.
Unary language
In computational complexity theory, a unary language or tally language is a formal language (a set of strings) where all strings have the form 1k, where "1" can be any fixed symbol.
In computational complexity theory, a unary language or tally language is a formal language (a set of strings) where all strings have the form 1k, where "1" can be any fixed symbol.
Unique games conjecture
In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002.
In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002.
Universal hashing
Using universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property.
Using universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property.
Weakly NP-complete
In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard), if there is an algorithm for the problem whose running time is polynomial in the dimen...
In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard), if there is an algorithm for the problem whose running time is polynomial in the dimen...
Yao's principle
In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of any randomized algorithm for solving a given problem, on the worst case inpu...
In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of any randomized algorithm for solving a given problem, on the worst case inpu...