Polynomial tree-stack realizers compile to Mathlib TM2
ProvedMetricSelfDualCompletion.RuntimeBridge.realizer_polytime_of_volume_boundcomplexity-theorycomputabilityruntimeturing-machines
Let F be a function on finite bit strings, realized by one fixed finite tree-stack routine R. Suppose that the sum of its execution charge and output tree volume is bounded by C times the d-th power of one plus the input tree volume, for fixed natural numbers C and d. Then F is computed by a deterministic Mathlib multi-stack TM2 in polynomial time in the input bit length. The machine begins with only the input stack populated and halts with precisely the output stack populated. This provides a reusable, exact bridge between the published stack-routine and PvsNP machine models; it is used for the uniform algorithms in STOC 2027 submission #5.
Preamble
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_ThreeMachine import Definitions.Def_OAIThreeMachineSched01
Formal statement
namespace MetricSelfDualCompletion.RuntimeBridge
open OAI.ThreeMachine.StackCompiler
/-- A fixed tree-stack routine with polynomial charge and polynomial output volume has a deterministic polynomial-time Mathlib TM2 implementation. -/
theorem realizer_polytime_of_volume_bound {F : List Bool → List Bool} (R : Realizer F)
(hR : ∃ C d : ℕ, ∀ xs, volume (F xs)+R.time xs ≤ C*(volume xs+1)^d) :
PvsNP.PolyTimeComputable F := by sorry
end MetricSelfDualCompletion.RuntimeBridgeSource
Mathlib Computability/TMComputable, Mathlib TM2 multi-stack machine; public OAI.ThreeMachine StackCompiler definitions and accepted OPIBridge.cookLevin_of_realizer proof (1edbb7d5-e07d-4897-a324-082389f13991, accepted89916395-3552-48c7-a656-01fb2462d0df, compiler fragment unchanged); Metric Self-Dual Completion, STOC 2027 #5, Lemma12 construction-time claim, printed p.10 / PDF p.12.