Polynomial log-cost RAM simulation of a binary list computation
ProvedTimeSpaceMA.widthListComputable_to_coinFreeRAMcomplexity-theorypseudorandomnessturing-machine
Let a deterministic polynomial-time multitape machine compute a finite list of naturals from a triple using a unary width and binary values for the other two fields. Then there is one coin-free log-cost RAM program and an exponent such that for every , , and , starting with in memory halts with work at most . At halt cell zero holds the list length and consecutive cells from address one hold the list entries.
This is the reverse machine-model transfer and output convention needed for a uniform neighbor listing. The unary width lets the source computation take polynomial time in even for small numerical labels.
Preamble
import Definitions.Def_TimeSpaceMA_RAM import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_List import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Nat import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Pair import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Unary
Formal statement
namespace TimeSpaceMA
open Turing.MultiTapeTM
/-- Compile a polynomial-time binary list computation to the log-cost RAM's length and
consecutive-record output convention. The width is provided in unary to the source machine. Only valid width, entropy, and vertex triples need
be simulated within the width-based polynomial cost bound. -/
theorem widthListComputable_to_coinFreeRAM
(listing : ℕ × ℕ × ℕ → List ℕ)
(hlisting : ComputableInPolyTime listing (encPair encUnary (encPair encNat encNat))
(encList encNat)) :
∃ (e : ℕ) (P : Program), P.CoinFree ∧
∀ n k v : ℕ, 1 ≤ n → k ≤ n → v < 2^n →
∃ st, P.RunsTo zeroTape (memOf [n,k,v]) st ∧ st.work ≤ n^e+e ∧
st.mem 0 = (listing (n,k,v)).length ∧
∀ i : Fin (listing (n,k,v)).length, st.mem (1+i.val) = (listing (n,k,v))[i] := by sorry
end TimeSpaceMA
Source
Cook and Reckhow, Time Bounded Random Access Machines, JCSS 7 (1973), Theorem 2(b), https://www.cs.toronto.edu/~sacook/homepage/rams.pdf. Adapted to the published log-cost RAM, finite binary list I/O, and the polynomial bound in the width.