Computational complexity theory classifies computational problems by the resources needed to solve them.
A decision problem asks for one of two answers, conventionally encoded as zero and one. Equivalently, it asks whether an input belongs to a formal language.
A search problem asks for a witness satisfying a specified relation rather than only whether one exists.
A search-to-decision reduction reconstructs a witness by making queries that only decide whether a suitable witness exists.
A complexity class is a collection of computational problems sharing specified resource bounds and a computational model.
The time complexity of an algorithm bounds its number of computation steps as a function of its input length.
An algorithm runs in polynomial time when its running time is at most for some constant , where is the input length.
is the class of decision problems whose positive instances have polynomial-length certificates verifiable in polynomial time. Equivalently, it is polynomial time on a nondeterministic computation.
A certificate for a positive instance is a polynomial-length string that makes a polynomial-time verifier accept that instance.
The space complexity of an algorithm bounds the amount of working memory it uses as a function of input length.
A decision problem is NL-complete when it belongs to NL and every problem in NL reduces to it by a deterministic logarithmic-space many-one reduction.
The directed graph reachability problem asks whether a directed graph contains a directed path from a specified vertex to a specified vertex . It is NL-complete.
The configuration graph of a machine on a fixed input has one vertex for each machine configuration and a directed edge for each valid computation step.
consists of complements of languages in NL.
The Immerman–Szelepcsényi theorem states that . Its proof uses inductive counting of reachable configurations.
Inductive counting certifies the number of vertices reachable within successively larger path-length bounds. Knowing the exact earlier count lets a logarithmic-space nondeterministic machine certify that no reachable predecessor has been omitted.
A polynomial-time many-one reduction from a decision problem to a decision problem is a polynomial-time computable function satisfying exactly when .
Quadratic-equation satisfiability over asks whether a finite system of polynomial equations of degree at most two over the finite field has a common solution.
A Boolean circuit is a finite directed acyclic graph of Boolean gates with designated inputs and outputs.
The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.
A circuit family contains one circuit for each input length . The circuit for one length may be chosen independently of those for other lengths, so a family is a nonuniform model of computation.
The polynomial hierarchy consists of decision problems described by a constant number of alternating polynomially bounded existential and universal quantifiers with a polynomial-time predicate.
A language is in when membership has the form for a polynomial-time predicate and polynomially bounded strings. Reversing the quantifiers defines .
The Karp–Lipton theorem states that implies that the polynomial hierarchy collapses to its second level.
Primality testing is the decision problem of determining whether an input integer is a prime number.
The Agrawal–Biswas primality test checks the identity modulo and a random low-degree monic polynomial. Prime inputs always pass, while a composite input that is not a prime power fails with inverse-polynomial probability per trial.
Articles by others on the same topic
Computational complexity theory is a branch of theoretical computer science that studies the resources required for solving computational problems. The primary focus is on classifying problems according to their inherent difficulty and understanding the limits of what can be computed efficiently. Here are some key concepts and elements of computational complexity theory: 1. **Complexity Classes**: Problems are grouped into complexity classes based on the resources needed to solve them, primarily time and space.