Word-RAM specification for exact clique counting
DefinitionVWZClique_CountAn accepting program must return the number of unordered cliques in the first output word. The word width grows logarithmically with graph order.
import Mathlib
import Definitions.Def_MonDepMW_RunsWithin
namespace VWZClique
open Classical in
noncomputable def count {n : ℕ} (G : SimpleGraph (Fin n)) (k : ℕ) : ℕ :=
((Finset.univ.powersetCard k).filter fun s : Finset (Fin n) =>
∀ u ∈ s, ∀ v ∈ s, u ≠ v → G.Adj u v).card
def countsWithin (k : ℕ) (e : ℝ) : Prop :=
∃ (P : List TrulySubcubicAPSP.Instr) (b : ℕ) (C : ℝ), 0 < b ∧ 0 < C ∧
∀ (n : ℕ) (G : SimpleGraph (Fin n)), 2 ≤ n →
∃ t : ℕ, (t : ℝ) ≤ C * (n : ℝ) ^ e ∧
MonDepMW.RunsWithin P (b * (n.log2 + 1)) t (MonDepMW.graphInput G)
(fun out => out 0 = (count G k : ℤ))
end VWZClique
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6), independent blind auditor
For every natural number , every simple undirected graph on the vertices , and every natural number , the count is the number of -element subsets of the vertex set for which every two distinct vertices in are adjacent in . Each such subset contributes once. The count is for , is for , and is whenever . These conventions include the graph with no vertices.
For a natural number and a real number , the running-time predicate holds exactly when there exist a finite word-RAM program , a positive natural number , and a positive real number with the following property. For every natural number and every simple undirected graph on , there exists a natural number such that , started at instruction with word width exactly , accepts within instructions, including the accepting instruction. Initially cell holds , cells through hold the zero-one adjacency matrix of in row-major order, and all other integer-addressed cells hold zero, with each value stored modulo . Instructions may write the constant one, add, subtract or multiply words modulo , load or store indirectly using a signed word as an address, branch to a fixed instruction if a word is negative in signed interpretation, or accept or reject. Running past the program rejects. In the accepting memory, the signed integer in cell must equal the number of -element vertex subsets whose distinct members are pairwise adjacent. The predicate places no condition on the other final cells or on graphs with . For the required output is zero, and for it is one.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.