GLOBAL KNOWLEDGE ARK

Reference library

Foundations

Explore concepts, laws, equations and methods, with clear explanations of their use and sources. Choose an area of study or find a specific entry.

More filters

Reference entries

Showing 451–480 of 1709 reference entries

Mathematics & logicPolynomial division and greatest common divisors

Over a field F, f=gq+r has unique q,r for nonzero g, with r=0 or deg r<deg g.

MethodMathematics & logicIrreducibility and Eisenstein criterion

A nonconstant polynomial over F is irreducible if it cannot factor into two positive-degree polynomials over F.

MethodMathematics & logicChi-square distribution

The sum of squares of k independent standard normal variables has chi-square law χ²ₖ=Gamma(k/2,1/2), with mean k and variance 2k.

DefinitionMathematics & logicStudent t and the normal-mean pivot

If Z∼N(0,1) and U∼χ²ν are independent, Z/√(U/ν) has tν law.

MethodMathematics & logicParametric and empirical bootstrap

Recompute statistic T on many size-n simulated data sets.

MethodInformationMultitape simulation and model equivalence

A fixed finite-tape deterministic Turing machine running in time t(n)≥n can be simulated by a single-tape machine in O(t(n)²) time by storing tape contents and head markers and scanning them for each simulated step.

Mathematical statementInformationTime, space and encoded input size

A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length.

DefinitionMathematics & logicComparison and limit-comparison tests

For eventually nonnegative terms aₙ≤bₙ, convergence of Σbₙ implies convergence of Σaₙ; divergence of Σaₙ implies divergence of Σbₙ.

Mathematical statementMathematics & logicRatio and root convergence tests

If |aₙ₊₁/aₙ|→ρ, or |aₙ|¹⁄ⁿ→ρ, then Σaₙ converges absolutely for ρ<1 and diverges for ρ>1.

Mathematical statementMathematics & logicUniform convergence of derivatives

If differentiable real fₙ on (a,b) converge pointwise to f and fₙ′ converge uniformly to g, then f is differentiable and f′=g.

Mathematical statementMathematics & logicUniform limits and Riemann integration

If Riemann-integrable fₙ on a finite interval [a,b] converge uniformly to f, then f is Riemann integrable and ∫ₐᵇfₙ dx→∫ₐᵇf dx.

Mathematical statementMathematics & logicPower-series convergence and differentiation

For Σaₙ(x−c)ⁿ the radius R is 1/lim sup|aₙ|¹⁄ⁿ, with 1/0=∞ and 1/∞=0.

Mathematical statementMathematics & logicSum and product counting principles

Disjoint finite alternatives have total count equal to the sum of their counts.

MethodMathematics & logicInclusion–exclusion for overlapping sets

For finite A,B, |A∪B|=|A|+|B|−|A∩B|.

MethodMathematics & logicPermutations and combinations

From n distinct objects choose k without repetition.

MethodInformationFlow feasibility and max-flow/min-cut certificate

A directed network flow respects nonnegative capacities and conserves flow at vertices other than source s and sink t.

Mathematical statementInformationEdmonds–Karp augmenting-path algorithm

Starting with zero flow, find a shortest residual s–t path by breadth-first search and augment by its minimum residual capacity, updating forward and reverse capacities.

MethodInformationDiscrete Fourier transform and inverse

For N complex coefficients aⱼ define yₖ=Σ_(j=0)^(N−1)aⱼωᴶᴷ, with ω=e²πⁱ⁄ᴺ.

Mathematical statementInformationRadix-two fast Fourier transform

For N a power of two, split polynomial coefficients into even and odd indices, recursively transform each half, and combine values using p(z)=p_even(z²)+zp_odd(z²).

MethodMathematics & logicUnits, zero divisors and integral domains

A unit has a multiplicative inverse.

DefinitionMathematics & logicFraction field of an integral domain

For integral domain R, fractions a/b with b≠0 are equivalence classes under a/b=c/d iff ad=bc.

DefinitionMathematics & logicPrime and maximal ideals

For a commutative ring with identity and proper ideal I, I is prime iff ab∈I implies a∈I or b∈I, equivalently R/I is an integral domain.

Mathematical statementMathematics & logicField characteristic and prime subfields

A field has characteristic zero if no positive n satisfies n·1=0; otherwise its characteristic is a prime p.

DefinitionMathematics & logicUnique factorization and principal ideal domains

In an integral domain irreducibles are nonzero nonunits that cannot split into two nonunits; primes divide a product only by dividing a factor.

Mathematical statementMathematics & logicEuclidean division and the domain hierarchy

A Euclidean domain has a nonnegative integer size d on nonzero elements permitting b=aq+r with r=0 or d(r)<d(a), and d(a)≤d(ab).

Mathematical statementMathematics & logicField-extension degree and tower law

For fields F⊆K, degree [K:F] is dim_F K.

Mathematical statementMathematics & logicAlgebraic elements and minimal polynomials

An algebraic α satisfies a nonzero polynomial over F.

Mathematical statementMathematics & logicFinite fields and polynomial construction

A finite field has pⁿ elements for a prime p and n≥1; for every such size one exists uniquely up to isomorphism.

Mathematical statementMathematics & logicFinite Galois correspondence

A splitting field is generated by all roots of a polynomial; a separable polynomial has distinct roots.

Mathematical statementMathematics & logicScalar and vector line integrals

Along a piecewise C¹ regular path r(t), scalar integration is ∫C f ds=∫f(r(t))‖r′(t)‖dt and vector integration is ∫C F·dr=∫F(r(t))·r′(t)dt.

Method
DefinitionSource checked

Time, space and encoded input size

Information

A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length.

Key knowledge

A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length. The machine model and encoding are part of the statement: a number's magnitude is different from the length of its binary representation.

Conditions and scope

  • Specify whether input storage is included when giving a space bound.
  • Polynomial time remains a mathematical class, not a promise of practical speed for every polynomial exponent.
Sources · 1

References

Sources retain their recorded scope. A source link alone does not establish verification of every statement.

  1. 6.045J (2011), Lecture 12: Complexity theoryNancy Lynch / MITCourse notes · PDFocw.mit.eduRead source

Evidence and review

Lecture 12 slides 2, 6, 20–24 and 33: resource definitions, input-length worst case and model/feasibility limits.

2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.

Related reference entries

Explore relationships within this area of study and its connections to other areas.

Showing 1–10 of 10 relationships

Scientific relationships · 10 / 10

The relationship type describes the connection. Its linked statements, sources and conditions define the scope.

  1. Uses definition
    Relationship sources · 1

    Linked statements

    • A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length. The machine model and encoding are part of the statement: a number's magnitude is different from the length of its binary representation.
  2. Uses definition
    Relationship sources · 1

    Linked statements

    • A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length. The machine model and encoding are part of the statement: a number's magnitude is different from the length of its binary representation.
  3. Uses definition
    Relationship sources · 1

    Linked statements

    • A deterministic decider's time cost counts steps and its space cost counts used storage cells; worst-case bounds maximize over inputs of the same encoded length. The machine model and encoding are part of the statement: a number's magnitude is different from the length of its binary representation.
  4. Uses definition
    Relationship sources · 1

    Linked statements

    • For n records with integer keys 0≤k<U, append records to U insertion-ordered buckets by key, then concatenate buckets in increasing key order. This sorts stably in O(n+U) time and space with unit-cost indexing and appends. Duplicate keys retain their input order.
  5. Uses definition
    Relationship sources · 1

    Linked statements

    • Represent nonnegative integer keys with d base-B digits and stably sort each digit from least to most significant. After each pass the processed suffix is ordered, giving total O(d(n+B)) time with counting-sort passes. Choosing B=n makes bounded nᶜ keys linear-time for fixed c.
  6. Uses definition
    Relationship sources · 1

    Linked statements

    • In a finite integer-weighted DAG set d(s)=0 and other d(v)=∞, process vertices in topological order, and relax each outgoing u→v by d(v)←min(d(v),d(u)+w(u,v)). The resulting distances are exact, including with negative weights; the procedure costs O(|V|+|E|) in the unit-cost arithmetic model.
  7. Uses definition
    Relationship sources · 1

    Linked statements

    • For string suffixes A[i:],B[j:], let L(i,j) be their longest common subsequence length. Empty suffixes give zero; matching first characters give 1+L(i+1,j+1), otherwise max(L(i+1,j),L(i,j+1)). Filling indices backwards solves the problem in O((m+1)(n+1)) time and table space; predecessor choices recover a subsequence.
  8. Uses definition
    Relationship sources · 2

    Linked statements

    • DSPACE(s(n)) and NSPACE(s(n)) contain decision languages solvable with O(s(n)) workspace by deterministic and nondeterministic Turing machines. L=DSPACE(log n), NL=NSPACE(log n), PSPACE=⋃ₖ≥₁DSPACE(nᵏ), and NPSPACE=⋃ₖ≥₁NSPACE(nᵏ).
  9. Uses definition
    Relationship sources · 2

    Linked statements

    • 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. A space bound s(n)≥log n is space constructible here when its value can be computed from 1ⁿ in O(s(n)) workspace. These hypotheses allow a simulation to enforce its resource budget.
  10. Uses definition
    Relationship sources · 2

    Linked statements

    • 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)). Diagonal simulation with padding gives a language requiring more than the smaller time bound. In particular DTIME(n²)⊊DTIME(n³).
Entry detailsPermanent link to this entry ↗
Record identity
info-time-space-cost-model
Revision
university-core.1
Structured reference record
University core expansion