Foundations

A time bound t(n)≥n is time constructible here when a Turing machine on unary input 1ⁿ can write 1ᵗ⁽ⁿ⁾ in O(t(n)) time.

For a space-constructible s(n)≥log n, NSPACE(s(n))⊆DSPACE(s(n)²).

A logspace many-one reduction computes f with x∈A exactly when f(x)∈B, using a read-only input, O(log n) work tape and write-only output.

NL=coNL: complements of nondeterministic logspace decision languages also lie in NL.

For time-constructible f,g≥n with f(n)log f(n)=o(g(n)), DTIME(f(n)) is a proper subset of DTIME(g(n)).

If S is space constructible, S(n)≥n, and s(n)=o(S(n)), then DSPACE(s(n))⊊DSPACE(S(n)).

L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP, where EXP=⋃ₖ≥₁DTIME(2ⁿᵏ).

Boolean satisfiability SAT is NP-complete under polynomial-time many-one reductions.

Introduce variables for Boolean subformula gates, constrain each gate to agree with its inputs using clauses of at most three literals, and require the output gate true.

TQBF asks whether a fully quantified finite Boolean formula is true.

For any Turing machine T taking a machine description and ordinary input, a machine R can behave on input x as T does on (⟨R⟩,x).

For every context-free language L, some p≥1 makes every w∈L with |w|≥p decomposable as w=uvxyz with |vxy|≤p, |vy|≥1 and uvⁱxyⁱz∈L for every integer i≥0.

The language {0ⁿ1ⁿ2ⁿ:n≥0} is not context free.

Context-sensitive productions replace αAβ by αγβ with γ nonempty; equivalently, their nonempty-word languages admit noncontracting productions u→v with |u|≤|v| and a nonterminal in u.

An ideal baseband signal containing no frequencies above B can be reconstructed from exact uniform samples at f_s>2B.

For a uniform rounding quantizer with step Δ and no overload, the error magnitude is at most Δ/2.

A randomized mechanism is (epsilon,delta)-differentially private if every neighboring dataset pair and every output event obey Pr[M(D) in S]≤exp(epsilon)Pr[M(D-prime) in S]+delta.

For a vector query with global L1 sensitivity Delta-1, adding independent Laplace noise of scale Delta-1/epsilon to each coordinate gives epsilon-DP under the chosen adjacency.

For order alpha>1, RDP bounds the Rényi divergence between mechanism outputs on every adjacent dataset pair by epsilon-alpha.

A norm-bounded adversarial evaluation asks whether an attacker can change a model's prediction using perturbations within a specified set around an input.

Gaussian smoothing defines a classifier by the most probable prediction of a base classifier under N(0,sigma²I) noise.

Scaled dot-product attention computes softmax(QK-transpose/sqrt(d-k))V, allowing token representations to combine context through learned query/key/value projections.

A DDPM adds Gaussian noise in a forward Markov chain and learns a parameterized reverse process to generate samples.

An autoregressive model factors a sequence law into conditional next-element distributions, while a diffusion model generates through a learned reverse noise process.

Samuel, Zhou and Zou's COLING 2025 study compares five contamination-detection approaches across four language models and eight benchmarks, including a controlled fine-tuning oracle setting.

A code subspace with projector P exactly corrects a specified span of errors E-a precisely when P E-a† E-b P=c-ab P for every error pair.

A stabilizer code is the common fixed subspace of an abelian Pauli subgroup excluding minus identity.

Surface/toric codes measure local stabilizer checks and infer error chains from syndromes.

Fault-tolerant computation must control faults during syndrome extraction, recovery and encoded gates as well as idle storage.

Google Quantum AI's Nature study, online 9 December 2024 and in the 2025 volume, reports a distance-seven surface-code memory using 101 physical qubits with logical error 0.143%±0.003% per cycle.