Foundations

In a metric space, K is compact exactly when every sequence in K has a subsequence converging to a point in K.

Uniform continuity requires one δ>0 for each ε>0 to control d_Y(f(p),f(q))<ε whenever d_X(p,q)<δ, for all p,q.

For a complex 2π-periodic Riemann-integrable f, cₙ=(2π)⁻¹∫₋π^πf(x)e⁻ⁱⁿˣdx and s_N=Σ|n|≤N cₙeⁱⁿˣ satisfy ∫|f−s_N|²→0.

For a real sequence, lim sup xₙ=lim_N sup{k≥N}xₖ and lim inf xₙ=lim_N inf{k≥N}xₖ.

A space X is simply connected when it is path connected and every continuous loop based at a∈X deforms to the constant loop while keeping its endpoints at a.

DSPACE(s(n)) and NSPACE(s(n)) contain decision languages solvable with O(s(n)) workspace by deterministic and nondeterministic Turing machines.

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.

A real n×n matrix A is diagonalizable over ℝ exactly when it has n linearly independent real eigenvectors.

For a finite square matrix A over a field, its characteristic polynomial p(t)=det(tI−A)=tⁿ+cₙ₋₁tⁿ⁻¹+⋯+c₀ satisfies p(A)=Aⁿ+cₙ₋₁Aⁿ⁻¹+⋯+c₀I=0.

If Nʳ=0 and A=λI+N, then eᵗᴬ=e^(λt)Σₖ₌₀ʳ⁻¹tᵏNᵏ/k!.

A closed quantum system evolves by iħ d|ψ⟩/dt=H(t)|ψ⟩.

For a time-independent Hamiltonian, an energy eigenstate evolves by a phase exp(−iEt/ħ).

With zero potential inside 0<x<L and impenetrable walls, normalized eigenfunctions are √(2/L) sin(nπx/L) and energies are n²π²ħ²/(2mL²), n=1,2,… .

A real one-dimensional potential conserves probability current.

For H=p²/(2m)+mω²x²/2 on the real line, normalizable states have E_n=ħω(n+½), n=0,1,… .

For the canonical oscillator, a=√(mω/(2ħ))x+ip/√(2mħω) and its adjoint satisfy [a,a†]=1.

The Heisenberg observable A_H=U†A_SU obeys dA_H/dt=(i/ħ)[H_H,A_H]+(∂A_S/∂t)_H.