Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniformity bridge — a family serialized by Cook–Levin machines on raw prefixes is a uniform resource family

Proved
TwoFoldOPI.uniformFamily_of_CLSerializableF

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

optimal-polynomial-intersectionquantum-algorithmsturing-machinesuniformity

Let x↦construct(x)x\mapsto\mathrm{construct}(x)x↦construct(x) assign a concrete quantum program to every instance xxx of Theorem 7.4. Suppose two polynomial-time Cook–Levin machines read the zero-padded prefix enc(x)[s]\mathrm{enc}(x)_{[s]}enc(x)[s]​ of the instance encoding and

  • the decider outputs true exactly when ∣enc(x)∣≤s|\mathrm{enc}(x)|\le s∣enc(x)∣≤s and m+r+q+t≤sm+r+q+t\le sm+r+q+t≤s (and false otherwise);
  • the generator outputs the canonical serialization of construct(x)\mathrm{construct}(x)construct(x) whenever the prefix is long enough in this sense.

Then there is a UniformResourceFamily over the instances, with encoding enc\mathrm{enc}enc and size parameter m+r+q+tm+r+q+tm+r+q+t, whose programs are exactly construct(x)\mathrm{construct}(x)construct(x). That is, there are one public bit program (no coins, no oracle queries) and one polynomial BBB such that, on the bare encoding enc(x)\mathrm{enc}(x)enc(x) with no end marker, the bit program halts successfully with output ser(construct(x))\mathrm{ser}(\mathrm{construct}(x))ser(construct(x)), within B(m+r+q+t)B(m+r+q+t)B(m+r+q+t) 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.

Preamble
import Mathlib
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_TwoFoldOPI_CLSerializableF
Formal statement
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
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held), §7.3, Theorem 7.4, p.40 ("running in poly(m, q, log(1/ϵ)) time") and §5.2, "Computational conventions", p.26.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me