Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Binary TM simulation of Teutsch’s folded disperser neighbor queries

Proved
CNFEncComplexity.teutschNbr_polytime

by bersubs · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

cnf-encodingscomputational-complexitydisperserturing-machine

Let PPP be a fixed, coin-free log-cost RAM program and let e,C,ae,C,ae,C,a be fixed natural numbers. On a binary query (N,k,ℓ,i)(N,k,\ell,i)(N,k,ℓ,i), set n=⌊log⁡2N⌋+1n=\lfloor\log_2 N\rfloor+1n=⌊log2​N⌋+1 and use the degree budget anaa n^aana to decode iii into a layer and a local slot. Reject layers outside the range of kkk or above ⌊log⁡2N⌋\lfloor\log_2 N\rfloor⌊log2​N⌋, and reject ℓ≥N\ell\ge Nℓ≥N.

For a valid layer jjj, simulate PPP on (n,j,ℓ)(n,j,\ell)(n,j,ℓ) for ne+en^e+ene+e steps starting with zero-filled memory elsewhere. Treat a halted state’s cell zero as the list length and cells 1,2,…1,2,\ldots1,2,… as the entries. An existing entry at the decoded slot is folded by a power-of-two residue and copy index and translated into its disjoint layer interval. The query returns no label when the program has not halted or the slot is out of range.

The resulting optional label function has a deterministic multitape Turing machine running in time polynomial in the binary query length. The machine may depend on P,e,C,aP,e,C,aP,e,C,a. The result supplies the bit-model implementation of the explicit neighbor algorithm independently of the disperser coverage theorem.

Formalization Note The query and result are encoded by encNbrIn and encOptNat. The functions mergeNbr and ramFoldedLayer specify the slot decoding, folding and treatment of invalid inputs.

Preamble
import Mathlib.Computability.TuringMachine.Computable
import Definitions.Def_CNFEncComplexity_encNbrIn
import Definitions.Def_CNFEncComplexity_teutschNbr
Formal statement
namespace CNFEncComplexity

/-- The binary evaluator for the disjoint union of folded log-cost RAM neighbor lists
has a polynomial-time multitape implementation. -/
theorem teutschNbr_polytime (P : TimeSpaceMA.Program) (e C a : ℕ)
    (hP : P.CoinFree) :
    Nonempty (Turing.TM2ComputableInPolyTime encNbrIn encOptNat
      (mergeNbr (fun N => a * (Nat.log 2 N + 1)^a) (ramFoldedLayer P e C))) := by sorry

end CNFEncComplexity
Source
Jason Teutsch, Short lists for shortest descriptions in short time, https://arxiv.org/pdf/1212.6104, §4, pp. 6–8, Theorem 4 and Expander Lemma (binary machine implementation of the neighbor algorithm).

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