A Turing machine is an abstract computational model with a finite control, an unbounded tape and a head that reads, writes and moves on the tape.
In a deterministic computation, every configuration and input symbol determine at most one next configuration.
A reversible computation has an injective transition function, so its preceding configuration can be recovered from its current configuration. Any finite classical computation can be simulated reversibly while retaining enough workspace to uncompute its temporary results.
A reversible circuit is composed of bijective gates. The Toffoli gate is universal for reversible Boolean computation when ancillary bits are available.
A nondeterministic computation may have several possible next configurations and accepts when at least one computation path accepts.
Logical negation exchanges zero and one.
The conjunction is one exactly when both inputs are one.
The disjunction is one exactly when at least one input is one.
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
Theoretical computer science is a branch of computer science that focuses on the mathematical and abstract foundations of computing. It encompasses a variety of topics and concepts that explore the capabilities, limitations, and behavior of computational systems. Some of the key areas within theoretical computer science include: 1. **Algorithms and Complexity**: This area studies the efficiency of algorithms and classifies problems based on their computational complexity. It explores concepts such as P versus NP, NP-completeness, and various complexity classes (e.g.