Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A bounded uniform gate generator for consistent RAM memory

Proved
CNFEncComplexity.Robson.gateComponent_memory

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

complexity-theoryramsat

Fix an instruction-count bound PPP. A deterministic polynomial-time construction produces O((t+1)log⁡2(t+2))O((t+1)\log_2(t+2))O((t+1)log2​(t+2)) Boolean gates for the memory consistency test on the shared interval ports. An extension exists exactly when the occupied slots are well formed and each observation agrees with the last write to the same address, starting with all cells zero. The constant depends only on PPP.

Preamble
import Definitions.Def_CNFEncComplexity_RobsonConstraints
open CookLevin CNFEncComplexity
Formal statement
namespace CNFEncComplexity.Robson
theorem gateComponent_memory (P : ℕ) : GateComponent P 1 := by sorry
end CNFEncComplexity.Robson
Source
Sections 3.2–3.3. Robson, An O(T log T) reduction from RAM computations to satisfiability, TCS 82 (1991), pp. 141–149, https://www.sciencedirect.com/science/article/pii/0304397591901774. Adapted to the RAM of Krapivin–Przybocki–Subercaseaux, arXiv:2611.05614, Section 3, Theorem 10.

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