Žinių pagrindai

Metrinėje erdvėje K yra kompaktinė tada ir tik tada, kai kiekviena K elementų seka turi posekį, konverguojantį į K tašką.

Tolygusis tolydumas reikalauja, kad kiekvienam ε>0 būtų vienas δ>0, užtikrinantis d_Y(f(p),f(q))<ε visiems p,q, kuriems d_X(p,q)<δ.

Kai f yra kompleksinė 2π periodinė funkcija, integruojama Rymano prasme, cₙ=(2π)⁻¹∫₋π^πf(x)e⁻ⁱⁿˣdx ir s_N=Σ|n|≤N cₙeⁱⁿˣ tenkina ∫|f−s_N|²→0.

Realiųjų skaičių sekai lim sup xₙ=lim_N sup{k≥N}xₖ ir lim inf xₙ=lim_N inf{k≥N}xₖ.

Erdvė X yra vienasąryšė, kai ji yra keliais jungi ir kiekvieną tolydžią kilpą su baziniu tašku a∈X galima deformuoti į pastoviąją kilpą, jos galus išlaikant taške a.

DSPACE(s(n)) ir NSPACE(s(n)) apima sprendimo uždavinių kalbas, kurias deterministinės ir nedeterministinės Tiuringo mašinos atpažįsta naudodamos O(s(n)) darbinės atminties.

Laiko riba t(n)≥n čia vadinama konstruojama laiko atžvilgiu, jei Tiuringo mašina, gavusi unarinę įvestį 1ⁿ, gali per O(t(n)) laiko užrašyti 1ᵗ⁽ⁿ⁾.

Jei s(n)≥log n yra pagal atmintį konstruojama funkcija, tai NSPACE(s(n))⊆DSPACE(s(n)²).

Logaritminės atminties daugelio į vieną redukcija apskaičiuoja f taip, kad x∈A tada ir tik tada, kai f(x)∈B, naudodama tik skaitomą įvestį, O(log n) darbinę juostą ir tik rašomą išvestį.

NL=coNL: nedeterministine logaritmine atmintimi sprendžiamų kalbų papildiniai taip pat priklauso NL.

Laiko požiūriu konstruojamoms funkcijoms f,g≥n, kurioms f(n)log f(n)=o(g(n)), DTIME(f(n)) yra tikrasis DTIME(g(n)) poaibis.

Jei S yra atminties požiūriu konstruojama funkcija, S(n)≥n ir s(n)=o(S(n)), tai DSPACE(s(n))⊊DSPACE(S(n)).

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

Būlio formulių įvykdomumo uždavinys SAT yra NP pilnas pagal polinominio laiko daugelio į vieną redukcijas.

Įvesti kintamuosius Būlio poformulių loginiams elementams, ne daugiau kaip trijų literalų disjunkcijomis užtikrinti, kad kiekvieno elemento reikšmė atitiktų jo įvestis, ir reikalauti, kad išvesties elemento reikšmė būtų tiesa.

TQBF uždavinys klausia, ar visiškai kvantifikuota baigtinė Bulio formulė yra teisinga.

Bet kuriai Tiuringo mašinai T, gaunančiai mašinos aprašą ir įprastą įvestį, galima sudaryti mašiną R, kuri su įvestimi x elgiasi taip, kaip T su (⟨R⟩,x).

Kiekvienai bekontekstei kalbai L egzistuoja toks p≥1, kad kiekvieną w∈L, kuriam |w|≥p, galima išskaidyti kaip w=uvxyz taip, kad |vxy|≤p, |vy|≥1 ir uvⁱxyⁱz∈L kiekvienam sveikajam skaičiui i≥0.

Kalba {0ⁿ1ⁿ2ⁿ:n≥0} nėra bekontekstė.

Kontekstinės produkcijos pakeičia αAβ į αγβ, kai γ netuščias; lygiaverčiai, jų netuščių žodžių kalbas galima aprašyti netrumpinančiomis produkcijomis u→v, kur |u|≤|v|, o u turi neterminalą.

Realiąją n×n matricą A galima diagonalizuoti virš ℝ tada ir tik tada, kai ji turi n tiesiškai nepriklausomų realiųjų tikrinių vektorių.

Baigtinio dydžio kvadratinės matricos A virš lauko charakteristinis daugianaris p(t)=det(tI−A)=tⁿ+cₙ₋₁tⁿ⁻¹+⋯+c₀ tenkina tapatybę p(A)=Aⁿ+cₙ₋₁Aⁿ⁻¹+⋯+c₀I=0.

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

Uždaros kvantinės sistemos evoliuciją aprašo iħ d|ψ⟩/dt=H(t)|ψ⟩.

Kai hamiltonianas nepriklauso nuo laiko, energijos tikrinė būsena evoliucionuoja įgydama fazės daugiklį exp(−iEt/ħ).

Kai potencialas srityje 0<x<L lygus nuliui, o sienelės nepralaidžios, normuotos tikrinės funkcijos yra √(2/L) sin(nπx/L), o energijos – n²π²ħ²/(2mL²), n=1,2,… .

Realus vienmatis potencialas išsaugo tikimybės srovę.

Kai H=p²/(2m)+mω²x²/2 realiojoje tiesėje, normuojamųjų būsenų energijos yra E_n=ħω(n+½), n=0,1,… .

Kanoniniam osciliatoriui a=√(mω/(2ħ))x+ip/√(2mħω) ir jo hermitiškai jungtinis operatorius tenkina [a,a†]=1.

Heizenbergo stebimasis dydis A_H=U†A_SU tenkina lygtį dA_H/dt=(i/ħ)[H_H,A_H]+(∂A_S/∂t)_H.