Padded instance encoding and RAM-serializable program families (Theorem 7.4)
DefinitionTwoFoldOPI_RAMSerializableTwo notions used to separate the uniformity requirement of Theorem 7.4 from the design of the algorithm.
- Padded encoding. For an instance of Theorem 7.4 with size parameter and public bit encoding (
TwoFoldOPI.Input.encode), the padded encoding is the bit string
A machine that runs in time polynomial in therefore runs in time polynomial in ; this is how the paper's (with , not ) is expressed for an ordinary machine whose running time is measured in its input length.
- RAM-serializability. A family of programs (
QAlgorithms.OPI.PackedMembershipProgram) is RAM-serializable if there are a uniform word-RAM algorithm (the publishedWordRAM.Complexitymodel, either instruction set) and a function on bit strings such that computes in polynomial time and
where is the canonical program serialization packedSerialization used by UniformResourceFamily.
This is the hypothesis of the bridge theorem TwoFoldOPI.uniformFamily_of_RAMSerializable, which turns any RAM-serializable family into a UniformResourceFamily (a public bit-program constructor), so that the algorithm of Theorem 7.4 can be programmed and verified on the word RAM instead of the low-level bit machine.
Formalization Note. RAMPolyTimeComputable A f is the published notion: , run at its canonical word width, halts within steps on every input of length with output of the input. is unconstrained on strings that are not padded 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
/-- **The padded instance encoding.** The bit string `1^{scale x} 0 · encode x`: the size
parameter `scale x = m + r + q + t` in unary, a separator `0`, then the public encoding of the
instance. A machine reading it may spend time polynomial in its length, i.e. polynomial in
`m + r + q + t` (the instance encoding itself has length polynomial in `scale x`). -/
noncomputable def Input.padded (x : Input) : List Bool :=
List.replicate x.scale true ++ false :: x.encode
/-- **Polynomial-time serializability of a program family on the word RAM.** A family
`construct : Input → PackedMembershipProgram` is *RAM-serializable* if some uniform word-RAM
algorithm (published `WordRAM.Complexity` model, either instruction set) computes, in time
polynomial in the input length, a function `f` on bit strings that maps the padded encoding of
every instance `x` to the canonical serialization `packedSerialization (construct x)` of its
program. -/
def RAMSerializable (construct : Input → PackedMembershipProgram) : Prop :=
∃ (m : WordRAM.Model) (A : WordRAM.Complexity.Algorithm m) (f : List Bool → List Bool),
WordRAM.Complexity.RAMPolyTimeComputable A f ∧
∀ x : Input, f x.padded = packedSerialization (construct x)
end TwoFoldOPI