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.
noncomputable def Complexity.SecondOrderPolynomial.toNatPolynomial {ι : Type x} (bounds : ι → Polynomial ℕ) :
Replace every oracle-length symbol by a polynomial bound.
Equations
- One or more equations did not get rendered due to their size.
- Complexity.SecondOrderPolynomial.toNatPolynomial bounds (Complexity.SecondOrderPolynomial.const value) = Polynomial.C value
- Complexity.SecondOrderPolynomial.toNatPolynomial bounds Complexity.SecondOrderPolynomial.input = Polynomial.X
Instances For
@[simp]
theorem Complexity.SecondOrderPolynomial.toNatPolynomial_const {ι : Type x} (bounds : ι → Polynomial ℕ) (value : ℕ) :
@[simp]
theorem Complexity.SecondOrderPolynomial.toNatPolynomial_input {ι : Type x} (bounds : ι → Polynomial ℕ) :
@[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 : ℕ) :
Under polynomially bounded moduli, evaluation is bounded by the substituted polynomial.