Uniformity bridge — a family serialized by Cook–Levin machines on raw prefixes is a uniform resource family
ProvedTwoFoldOPI.uniformFamily_of_CLSerializableFLet assign a concrete quantum program to every instance of Theorem 7.4. Suppose two polynomial-time Cook–Levin machines read the zero-padded prefix of the instance encoding and
- the decider outputs
trueexactly when and (andfalseotherwise); - the generator outputs the canonical serialization of whenever the prefix is long enough in this sense.
Then there is a UniformResourceFamily over the instances, with encoding and size parameter , whose programs are exactly . That is, there are one public bit program (no coins, no oracle queries) and one polynomial such that, on the bare encoding with no end marker, the bit program halts successfully with output , within steps and visited cells.
This reduces the uniformity requirement of Theorem 7.4 to programming its classical constructor as polynomial-time Turing machines, for instance through OPIBridge.cookLevin_of_realizer.
Formalization Note. The hypothesis is TwoFoldOPI.CLSerializableF construct. The conclusion fixes the family's construct field to the given function.
import Mathlib import Definitions.Def_TwoFoldOPI_Input import Definitions.Def_QAlgorithms_Defs_OPIUniformity import Definitions.Def_TwoFoldOPI_CLSerializableF
namespace TwoFoldOPI
open QAlgorithms.OPI
/-- **Uniformity bridge (Cook–Levin version).** A program family that is serialized on raw
prefixes by polynomial-time Cook–Levin machines is a uniform resource family. -/
theorem uniformFamily_of_CLSerializableF (construct : Input → PackedMembershipProgram)
(h : CLSerializableF construct) :
∃ A : UniformResourceFamily Input Input.encode Input.scale, A.construct = construct := by
sorry
end TwoFoldOPI