A universal polynomial exponent for actual finite bit simulation
ProvedEdgeSublinearMWIS.Main.RamBridge.uniform_bit_simulationalgorithmscomputational-complexitygraph-theory
There is an integer such that every fixed finite word-RAM program has a finite binary stack program , a width polynomial and constant . If the encoded input and output fit the stated input-dependent word bound and runs in actual steps at width , where is input bit size, then
in at most actual stack steps. The exponent is selected before the RAM program.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem EdgeSublinearMWIS.Main.RamBridge.uniform_bit_simulation : ∃ (q : ℕ),
0 < q ∧
∀ (p : Lax808846.Ram.Program),
∃ (E : EdgeSublinearMWIS.Main.Program) (W : Polynomial ℕ) (K : ℕ),
0 < K ∧
(∀ (n : ℕ), 2 * n + 1 ≤ Polynomial.eval n W) ∧
∀ (xs ys : List ℕ) (t : ℕ),
Lax759944.RamPolytime.FitsInWords (2 * Lax759944.BinaryWordEncoding.bitSize xs + 1)
(xs.length :: xs ++ ys) →
Lax808846.Ram.RunsTo (Polynomial.eval (Lax759944.BinaryWordEncoding.bitSize xs) W) p (xs.length :: xs)
ys t →
EdgeSublinearMWIS.Main.Runs E (EdgeSublinearMWIS.Main.RamBridge.wordBits xs)
(EdgeSublinearMWIS.Main.RamBridge.wordBits ys)
(K * (Lax759944.BinaryWordEncoding.bitSize xs + t + 1) ^ q) := by sorrySource