Žinių pagrindai

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ą.

Idealų pagrindinės dažnių juostos signalą, kuriame nėra dažnių, aukštesnių už B, galima atkurti iš tikslių, vienodais laiko intervalais paimtų imčių, kai f_s>2B.

Tolygiojo apvalinančio kvantavimo įtaiso, kurio žingsnis Δ, paklaidos modulis, kai nėra perkrovos, neviršija Δ/2.

Randomizuotas mechanizmas užtikrina (epsilon,delta)-diferencialųjį privatumą, jei kiekvienai gretimų duomenų rinkinių porai ir kiekvienam išvesties įvykiui galioja Pr[M(D) in S]≤exp(epsilon)Pr[M(D-prime) in S]+delta.

Vektorinei užklausai, kurios globalusis L1 jautrumas yra Delta-1, prie kiekvienos koordinatės pridėjus nepriklausomą Laplaso triukšmą, kurio mastelio parametras yra Delta-1/epsilon, užtikrinamas epsilon diferencinis privatumas pagal pasirinktą gretimumo sąryšį.

Kai eilė alpha>1, RDP apriboja Rényi divergenciją tarp mechanizmo išvesčių kiekvienai gretimų duomenų rinkinių porai dydžiu epsilon-alpha.

Vertinant atsparumą priešiškoms atakoms su norma apribotais trikdžiais, klausiama, ar užpuolikas gali pakeisti modelio prognozę, naudodamas trikdžius iš nurodytos aibės aplink įvestį.

Gauso glodinimas apibrėžia klasifikatorių pagal labiausiai tikėtiną bazinio klasifikatoriaus prognozę, veikiant N(0,sigma²I) triukšmui.

Skaliarinės sandaugos dėmesio mechanizmas su mastelio korekcija apskaičiuoja softmax(QK-transpose/sqrt(d-k))V, todėl teksto vienetų reprezentacijos gali apjungti kontekstą per išmoktas užklausų, raktų ir reikšmių projekcijas.

DDPM prideda Gauso triukšmo tiesioginėje Markovo grandinėje ir išmoksta parametrizuotą atvirkštinį procesą imtims generuoti.

Autoregresinis modelis išskaido sekos tikimybinį dėsnį į sąlyginius kito elemento skirstinius, o difuzinis modelis generuoja taikydamas išmoktą atvirkštinį triukšmo procesą.

Samuel, Zhou ir Zou COLING 2025 tyrime lyginami penki duomenų užterštumo aptikimo metodai, taikomi keturiems kalbos modeliams ir aštuoniems etaloniniams testams, įskaitant kontroliuojamą tiksliojo derinimo aplinką su orakulu.

Kodo poerdvis su projektoriumi P tiksliai ištaiso nurodyto klaidų E-a tiesinio apvalkalo klaidas tada ir tik tada, kai kiekvienai klaidų porai galioja P E-a† E-b P=c-ab P.

Stabilizatoriaus kodas yra bendras visų abelinio Pauli pogrupio operatorių fiksuojamas poerdvis; pogrupyje negali būti minus vienetinis operatorius.

Paviršiniai ir toriniai kodai matuoja vietines stabilizatoriaus patikras ir pagal sindromus sprendžia apie galimas klaidų grandines.

Klaidoms atspariuose skaičiavimuose būtina valdyti klaidas išgaunant sindromą, atkuriant būseną ir vykdant užkoduotus loginius vartus, taip pat saugant būseną be operacijų.

„Google Quantum AI“ tyrime, paskelbtame žurnale Nature internete 2024 m. gruodžio 9 d. ir 2025 m. tome, aprašoma paviršiaus kodo atmintis, kurios kodo atstumas yra septyni ir kuri naudoja 101 fizinį kubitą, kurios loginės klaidos tikimybė per ciklą yra 0.143%±0.003%.