Program families serialized by a word-RAM algorithm on zero-padded prefixes of the instance encoding (Theorem 7.4)
DefinitionTwoFoldOPI_RAMSerializableFRAM-serializability on raw prefixes. For an instance of Theorem 7.4 with public bit encoding and size parameter , write for the first bits of .
A family of programs (QAlgorithms.OPI.PackedMembershipProgram) is RAM-serializable on raw prefixes if there are a uniform word-RAM algorithm (the published WordRAM.Complexity model, either instruction set) and a function on bit strings such that computes in polynomial time and, for every instance and every ,
where is the canonical serialization packedSerialization used by UniformResourceFamily.
The algorithm reads the self-delimiting instance encoding from a zero-padded prefix. It reports whether the prefix is long enough, and when it is, it outputs the program. A running time polynomial in is polynomial in once . This is the hypothesis of the bridge TwoFoldOPI.uniformFamily_of_RAMSerializableF.
Formalization Note. RAMPolyTimeComputable A F is the published notion: , at its canonical word width, halts within steps with output of its input. is unconstrained on strings that are not zero-padded prefixes of encodings.
import Mathlib
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_WordRAM_Complexity_BitIO
namespace TwoFoldOPI
open QAlgorithms.OPI
/-- **RAM-serializability on raw prefixes.** A program family `construct` is serialized by a
polynomial-time word-RAM algorithm working on zero-padded prefixes of the instance encoding: on the
first `s` bits of `encode x ++ 0^∞` the algorithm outputs `true` followed by the canonical
serialization of `construct x` once the prefix contains the whole encoding and `s` is at least the
size parameter `m + r + q + t`, and outputs `[false]` otherwise. -/
def RAMSerializableF (construct : Input → PackedMembershipProgram) : Prop :=
∃ (m : WordRAM.Model) (A : WordRAM.Complexity.Algorithm m) (F : List Bool → List Bool),
WordRAM.Complexity.RAMPolyTimeComputable A F ∧
∀ (x : Input) (s : ℕ), F ((x.encode ++ List.replicate s false).take s) =
if x.encode.length ≤ s ∧ x.scale ≤ s then true :: packedSerialization (construct x)
else [false]
end TwoFoldOPI