Computer science

An algorithm is a finite, precise procedure for transforming an input into an output.

A randomized algorithm makes some choices using random bits.

A probabilistic Turing machine is a Turing machine whose transitions may depend on independent random bits.

A randomized decision algorithm has one-sided error when one answer is always correct and only the other answer can be mistaken.

$\mathbf{RP}$ contains decision problems with a polynomial-time randomized algorithm that rejects every negative instance and accepts every positive instance with probability at least one half.

$\mathbf{co}\text{-}\mathbf{RP}$ consists of complements of languages in RP. Its algorithms always accept positive instances and reject negative instances with probability at least one half.

$\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{co}\text{-}\mathbf{RP}$. Equivalently, it consists of problems having an always-correct randomized algorithm with polynomial expected running time.

Independent repetitions reduce a randomized algorithm's error probability while preserving polynomial running time.

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

A formal language is a set of finite strings over a fixed finite alphabet.

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.

An oracle machine may query membership in a fixed language in one computation step.

A relativized complexity class ${\mathcal{C}}^A$ allows every machine defining $\mathcal{C}$ to query the same oracle $A$.

A Boolean operation maps one or more bits to a bit.

Logical negation exchanges zero and one.

The conjunction $u\wedge v$ is one exactly when both inputs are one.

The disjunction $u\vee v$ is one exactly when at least one input is one.

Computational complexity theory classifies computational problems by the resources needed to solve them.

A computational problem specifies the required output for every permitted input.

An input is the finite data supplied to a computation.

An output is the data produced by a computation.

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 $O(n^k)$ for some constant $k$, where $n$ is the input length.

$\mathbf{P}$ is the class of decision problems decidable by a deterministic computation in polynomial time.

$\mathbf{NP}$ 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 logarithmic-space computation uses $O(\log n)$ work-tape cells on inputs of length $n$.

$\mathbf{L}$ consists of decision problems solvable by a deterministic logarithmic space computation.

$\mathbf{NL}$ consists of decision problems solvable by a nondeterministic logarithmic space computation.

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 $s$ to a specified vertex $t$. 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.

$\mathbf{co}\text{-}\mathbf{NL}$ consists of complements of languages in NL.

The Immerman–Szelepcsényi theorem states that $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. 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 $A$ to a decision problem $B$ is a polynomial-time computable function $r$ satisfying $x\in A$ exactly when $r(x)\in B$.

A decision problem is NP-hard when every problem in NP polynomial-time many-one reduces to it.

A decision problem is NP-complete when it is both in NP and NP-hard.

The Boolean satisfiability problem asks whether a Boolean formula has an assignment making it true.

Quadratic-equation satisfiability over ${\mathbb{F}}_2$ asks whether a finite system of polynomial equations of degree at most two over the finite field ${\mathbb{F}}_2$ has a common solution.

If $\mathbf{P}\ne \mathbf{NP}$, then NP contains a decision problem that is neither in P nor NP-complete.

Circuit complexity studies the size and depth of circuits computing finite-input functions.

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 $(C_n)$ contains one circuit for each input length $n$. The circuit for one length may be chosen independently of those for other lengths, so a family is a nonuniform model of computation.

A circuit family has polynomial size when $C_n$ has at most $n^{O(1)}$ gates.

$\mathbf{P}/\mathrm{poly}$ is the class of decision problems decided by polynomial-size circuit families.

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 ${\Sigma }_2^{\mathbf{P}}$ when membership has the form $\exists u\forall vR(x,u,v)$ for a polynomial-time predicate $R$ and polynomially bounded strings. Reversing the quantifiers defines ${\Pi }_2^{\mathbf{P}}$.

The Karp–Lipton theorem states that $\mathbf{NP}\subseteq \mathbf{P}/\mathrm{poly}$ 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 $(X+1{)}^n=X^n+1$ modulo $n$ 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.