Realizers of polynomial charge compile to polynomial-time Cook–Levin machines
ProvedOPIBridge.cookLevin_of_realizerLet be a function on bit strings. Suppose has a realizer in the OAI routine framework (OAI.ThreeMachine.StackCompiler.Realizer): a register program over binary trees whose input–output behaviour on the tree encoding of bit strings is , with charge . Suppose there are such that, for every bit string ,
Then there are a legal multitape Cook–Levin machine (with some number of tapes and alphabet size ) and constants such that computes in time on inputs of length .
The routine framework lets one write a classical algorithm as a composition of combinators (pairing, composition, folds over lists, branching, iteration, unary arithmetic) with a charge that is computed alongside. This theorem turns such a functional program into a polynomial-time machine in the Cook–Levin cost model, the model used by the uniformity bridges OPIBridge.bitProgram_prefixSearch and TwoFoldOPI.uniformFamily_of_CLSerializableF.
Formalization Note. Running time and legality are the published CookLevin.ComputesInTime (halting with output on the last tape after exactly steps) and CookLevin.TuringMachine (the input tape is read-only). The output-length hypothesis is needed because a Cook–Levin machine must write its output.
import Mathlib import Definitions.Def_OAIThreeMachineSched01 import Definitions.Def_CookLevin_Cost
namespace OPIBridge
/-- **Realizers compile to polynomial-time Cook–Levin machines.** A function on bit strings with
an OAI `Realizer` of polynomial charge and polynomially bounded output is computed by a legal
polynomial-time Cook–Levin machine. -/
theorem cookLevin_of_realizer {F : List Bool → List Bool}
(R : OAI.ThreeMachine.StackCompiler.Realizer F) (c d : ℕ)
(hR : ∀ x, R.time x ≤ CookLevin.polyBound c d x.length)
(hF : ∀ x, (F x).length ≤ CookLevin.polyBound c d x.length) :
∃ (N : CookLevin.Machine) (k G c' d' : ℕ), CookLevin.TuringMachine k G N ∧
CookLevin.ComputesInTime N k (CookLevin.polyBound c' d') F := by
sorry
end OPIBridge