Functions computable in time polynomial in the value of their argument; deterministic polynomial-time functions
DefinitionQuantumKtSoI_Supplement_PolyInValueA function is computable in time polynomial in the value of its argument if a deterministic machine, on input the binary expansion , halts on every branch within steps with output , for constants . A function on strings is computable in deterministic polynomial time if a deterministic machine on input halts within steps with output .
The first notion is the hypothesis on gap functions in Theorems 7.3, 7.10 and F.4; the second is used for reductions, parsers and self-reductions.
Formalization Note A deterministic machine is a valid coded machine without gate states, as in the base mission; "with output " is output probability one at the deadline. The paper names no input format for ; with a bound polynomial in the value , unary and binary inputs give the same class.
import Mathlib
import Definitions.Def_QuantumKtSoI_pair
import Definitions.Def_QuantumKtSoI_CodedMachine
open Classical
noncomputable section
namespace QuantumKtSoI.Supplement
/-- `g : ℕ → ℕ` is **computable in time polynomial in the value of its argument** (Theorems 7.3,
7.10, F.4; Myrisiotis, STOC 2027 submission, held version sha256 6616571c…, pp.100, 110, 235): a
deterministic machine (a valid coded machine without gate states) on input `b(λ)` halts on every
branch within `c(λ+2)^k` steps with output `b(g(λ))` with probability one.
**Formalization Note** The paper names no input format; with a time bound polynomial in the value
`λ`, unary and binary inputs give the same class of functions. -/
def PolyInValue (g : ℕ → ℕ) : Prop :=
∃ F : CodedMachine, F.Valid ∧ F.GateFree ∧ ∃ c k : ℕ, ∀ lam : ℕ,
F.toMachine.HaltsWithin (bin lam) (c * (lam + 2) ^ k) ∧
F.toMachine.outputProb (bin lam) (c * (lam + 2) ^ k) (bin (g lam)) = 1
/-- A function `f` on strings is **computable in deterministic polynomial time** (p.18): a valid
coded machine without gate states, on input `z`, halts on every branch within `c(|z|+2)^k` steps
with output `f(z)` with probability one. -/
def PolyTimeFn (f : List Bool → List Bool) : Prop :=
∃ F : CodedMachine, F.Valid ∧ F.GateFree ∧ ∃ c k : ℕ, ∀ z : List Bool,
F.toMachine.HaltsWithin z (c * (z.length + 2) ^ k) ∧
F.toMachine.outputProb z (c * (z.length + 2) ^ k) (f z) = 1
end QuantumKtSoI.Supplement