Documentation

PolyFun.Complexity.SecondOrderPolynomial.NatPolynomial

Ordinary polynomial bounds for second-order polynomials #

Substituting polynomial upper bounds for response moduli gives an ordinary polynomial bound. The moduli themselves need not be monotone: monotonicity of natural-coefficient polynomials suffices to control nested oracle applications.

Replace every oracle-length symbol by a polynomial bound.

Equations
Instances For
    @[simp]
    theorem Complexity.SecondOrderPolynomial.toNatPolynomial_const {ι : Type x} (bounds : ι → Polynomial ℕ) (value : ℕ) :
    toNatPolynomial bounds (const value) = Polynomial.C value
    @[simp]
    theorem Complexity.SecondOrderPolynomial.toNatPolynomial_add {ι : Type x} (bounds : ι → Polynomial ℕ) (left right : SecondOrderPolynomial ι) :
    toNatPolynomial bounds (left.add right) = toNatPolynomial bounds left + toNatPolynomial bounds right
    @[simp]
    theorem Complexity.SecondOrderPolynomial.toNatPolynomial_mul {ι : Type x} (bounds : ι → Polynomial ℕ) (left right : SecondOrderPolynomial ι) :
    toNatPolynomial bounds (left.mul right) = toNatPolynomial bounds left * toNatPolynomial bounds right
    @[simp]
    theorem Complexity.SecondOrderPolynomial.toNatPolynomial_oracle {ι : Type x} (bounds : ι → Polynomial ℕ) (interface : ι) (argument : SecondOrderPolynomial ι) :
    toNatPolynomial bounds (oracle interface argument) = (bounds interface).comp (toNatPolynomial bounds argument)
    theorem Complexity.SecondOrderPolynomial.eval_toNatPolynomial {ι : Type x} (bounds : ι → Polynomial ℕ) (q : SecondOrderPolynomial ι) (k : ℕ) :
    Polynomial.eval k (toNatPolynomial bounds q) = eval (fun (i : ι) (x : ℕ) => Polynomial.eval x (bounds i)) k q

    Substitution agrees exactly with evaluation at polynomial response moduli.

    theorem Complexity.SecondOrderPolynomial.eval_le_toNatPolynomial {ι : Type x} (bounds : ι → Polynomial ℕ) (length : ι → ℕ → ℕ) (hlength : ∀ (i : ι) (m : ℕ), length i m ≤ Polynomial.eval m (bounds i)) (q : SecondOrderPolynomial ι) (k : ℕ) :
    eval length k q ≤ Polynomial.eval k (toNatPolynomial bounds q)

    Under polynomially bounded moduli, evaluation is bounded by the substituted polynomial.