Repository navigation
Description
Sparse hard sets for NP and coNP, from the ROADMAP bullet "Sparse and tally sets" (#1351 covers the reductions). The goal is to add SPARSE and prove that a sparse set that is hard for coNP (Fortune) or for NP (Mahaney) under polynomial-time many-one reductions gives P = NP. Ogihara–Watanabe's bounded truth-table extension is a stretch goal.
Milestones
- M1:
SPARSEand Fortune's theorem. Define the class, give checked examples on both sides, bridge it toPPoly.of_sparse, and prove Fortune's theorem. The decider is the pruned search of theSATself-reduction tree, certified withComputableInPolyTime. - M2: Mahaney's theorem. Prune by left-set labels: drop the interval between two nodes with the same label, then keep a census-bounded prefix. This reuses M1's tree and census API.
- M3 (optional): Ogihara–Watanabe, for sparse sets that are
NP-hard underPolyTimeBTTReducible.- M3a, one query (
PolyTimeKTruthTableReducible 1, Grochow's Question 3.2): feat(Classes/Sparse): sparse sets hard under one-query reductions (#1819 M3a) #1943. - M3b, bounded truth-table (
k ≥ 2): open. The checked left-set source and a proposed split (conjunctive case, thenSPARSE ⊆ R_ctt(TALLY), thenPRUNE) are in this comment.
- M3a, one query (
Proposed statements
-- Complexity/Computability/Complexity/Classes/Sparse.lean
/-- At most `p n` members of `S` have encodings of length at most `n`, for a polynomially bounded `p`. -/
def SPARSE (enc : α ↪ List Bool) : Set (Set α) :=
{S | ∃ p : ℕ → ℕ, PolynomiallyBounded p ∧ ∀ n, {a | a ∈ S ∧ (enc a).length ≤ n}.encard ≤ p n}
theorem SPARSE.exists_card_le (h : S ∈ SPARSE enc) :
∃ c d : ℕ, ∀ n (s : Finset α), (∀ a ∈ s, a ∈ S ∧ (enc a).length ≤ n) → s.card ≤ c * (n + 1) ^ d
-- checked examples: tally words `{w | ∀ b ∈ w, b = true} ∈ SPARSE encBits`; `Set.univ ∉ SPARSE encBits`
-- bridge: `Cslib.Circuits.Boolean.PPoly.of_mem_SPARSE : (L : Set (List Bool)) ∈ SPARSE encBits → L ∈ PPoly`
-- M1, Complexity/Computability/Complexity/Classes/Sparse/Fortune.lean
theorem Fortune.SAT_mem_P {encB : β ↪ List Bool} {S : Set β} (hS : S ∈ SPARSE encB)
(h : PolyTimeReducible encCNF encB UNSAT S) : SAT ∈ P encCNF
theorem coNPHard.P_eq_NP_of_mem_SPARSE (hard : coNPHard encB S) (hS : S ∈ SPARSE encB)
{α : Type} (enc : α ↪ List Bool) : P enc = NP enc
-- M2, Complexity/Computability/Complexity/Classes/Sparse/Mahaney.lean
theorem Mahaney.SAT_mem_P (hS : S ∈ SPARSE encB) (h : PolyTimeReducible encCNF encB SAT S) :
SAT ∈ P encCNF
theorem NPHard.P_eq_NP_of_mem_SPARSE (hard : NPHard encB S) (hS : S ∈ SPARSE encB)
{α : Type} (enc : α ↪ List Bool) : P enc = NP enc
-- M3: the same conclusion from `PolyTimeBTTReducible encCNF encB SAT S`The P = NP conclusions follow the form of NPComplete.P_eq_NP_of_mem_P and Ladner.P_eq_NP_of_SAT_mem_P, which hold for every encoding of instances. Sparseness counts members whose encodings have length at most n, the census form used by the source below. It is equivalent to the slice form #{x : BitString n | L.slice n x} ≤ s n that PPoly.of_sparse uses, and the bridge lemma checks this. encard keeps the bound honest: an infinite set has census ⊤, not 0.
Existing notions considered
Language.slice(cslib) andCslib.Circuits.Boolean.PPoly.of_sparse: sparseness appears there only as a hypothesis on slice cardinalities. NoSPARSEclass exists and no census API. The new class takes an encoding,SPARSE enc : Set (Set α), likeP encandNP enc, so it composes withPolyTimeReducibleandcoNPHard.PPoly.of_mem_SPARSEreusesPPoly.of_sparse.PolyTimeReducible,NPHardandcoNPHard(Complexity/Reduction.lean);PolyTimeBTTReducible(Reduction/TruthTableVariants.lean), for M3.SAT,UNSAT,encCNF,SAT.verifier/SAT.assignmentandUNSAT_mem_coNP.SAT.unitsand the self-reduction come fromClasses/NP/SelfReduction.lean. The tree nodes are partial assignmentsa : List (Literal ℕ), and a node's formula isunits a ++ φ. Leaves are checked withSAT.verifier.- Plain loop certificates
ComputableInPolyTime.foldlWith_specanditerateWith_spec, together withfun_proplist rules (zipIdx,filter,idxOf,take).
Sources (checked at the source)
- K. Fluet, L. A. Hemaspaandra, C. M. Homan, Fortune's Bounty: Taming Complexity by Trimming Trees, arXiv:2608.12976v1 (2026). The sparse-set definition, with the census of strings of length at most
n, is Assignment page 5, item 2. The proof is Appendix B, "Solution to Question 1" (keep one node per label) and "Solution to Question 2" (more thanp(r(|F|))distinct labels force a satisfiable node). M1 uses a variant: instead of accepting at that point, it keeps the firstc + 1labelled nodes, so the loop is uniform. - S. Fortune, A note on sparse complete sets, SIAM J. Comput. 8(3):431–433, 1979. Cited for the theorem; locator not verified.
- S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, JCSS 25(2):130–143, 1982. Locator not verified. M2's design step will pin a checked proof source for the left-set argument.
- M. Ogihara, O. Watanabe, bounded truth-table reductions of NP sets to sparse sets, SIAM J. Comput. 1991. Locator not verified; pinned in M3's design step.
M1 changes no abstracts. Selecting the theorems as headlines is a separate editorial decision.
worker-claude-e6cf7b0d-sparse (Claude Code, Opus), for coordinator-claude-e6cf7b0d.
Activity
SamuelSchlesinger commentedon Oct 30, 2026
Claimed by
worker-claude-e6cf7b0d-sparse(Claude Code, Opus) on branchclaude/sparse-hard-sets, starting with M1.SamuelSchlesinger commentedon Oct 30, 2026
M1 is in #1834 (
SPARSEand Fortune's theorem): awaiting review.worker-claude-e6cf7b0d-sparseis starting M2 (Mahaney) on a stacked branch.refactor(Classes/Sparse): expose the self-reduction tree facts
SamuelSchlesinger commentedon Oct 30, 2026
M2 (Mahaney) is in #1838, stacked on #1834: awaiting review. It follows Agrawal's proof from Grochow's exposition (arXiv:1610.05825v1, Theorem 2.1, checked at the source). M3 (Ogihara–Watanabe, btt) is not started. —
worker-claude-e6cf7b0d-sparseSamuelSchlesinger commentedon Oct 30, 2026
Handoff from
worker-claude-e6cf7b0d-sparse(Claude Code, Opus). I am stopping here.SPARSEand Fortune's theorem): feat(Classes/Sparse): SPARSE and Fortune's theorem #1834, awaiting review. Hosted CI passes ata2f9dac64.c711656cd.NP-hard sets underPolyTimeBTTReducible): not started, and available.Suggested route for M3:
PolyTimeKTruthTableReducible 1with an arbitrary one-variable truth table. It needs only one change toMahaney.stage: label pairs by(f (a ∨ b), negated?). The rest of the M2 infrastructure is reusable:Fortune.expand,Mahaney.disj, the stage/iteration certificates andList.eraseDupsBy.Reusable pieces from M1 and M2:
ComputableInPolyTime.eraseDupsByWithInput, afun_proprule.Fortune.computableInPolyTime_verifier_units_append, for the leaves.Fortune.length_encNode_leandMahaney.length_encCNF_disj_le, for the size bounds.exists_card_le_of_mem_SPARSEtogether withimage_mem_SPARSE_encBits_iff, for the census bound.feat(Classes/Sparse): SPARSE and Fortune's theorem (cslib-community#1834
feat(Classes/Sparse): Mahaney's theorem (cslib-community#1838)
doc(roadmap): drop the landed Fortune and Mahaney theorems from the s…
SamuelSchlesinger commentedon Oct 31, 2026
Claimed M3 by
worker-claude-e6cf7b0d-sparse-btt(Claude Code, Opus) on branchclaude/sparse-btt-1819. Starting with the one-query case (Grochow, arXiv:1610.05825v1, Question 3.2), then the bounded truth-table case.SamuelSchlesinger commentedon Oct 31, 2026
M3 status from
worker-claude-e6cf7b0d-sparse-btt(Claude Code, Opus).SATreduces to a sparse problem by aPolyTimeKTruthTableReducible 1reduction, thenP = NP. The proof follows Grochow, arXiv:1610.05825v1, Question 3.2 (p. 4), which I checked in the PDF. The PR also factors the level-by-level tree search intoFortune.searchWithandFortune.acceptsWith, and Fortune's and Mahaney's procedures now use them.k ≥ 2queries, Ogihara–Watanabe): still open, with no Lean code yet. The remaining endpoint is:PolyTimeBTTReducible encCNF encB SAT SwithS ∈ SPARSE encBimpliesP = NP.Checked source for the left-set proof. V. Arvind, J. Köbler, M. Mundhenk, On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets, Ulmer Informatik-Berichte 92-01 (PDF dated 11 Feb 1993): https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui/Ulmer_Informatik_Berichte/1992/UIB_1992-01.pdf. I checked these locators in that PDF:
Left(A) ∈ R^p_b(R^p_ctt(SPARSE))impliesA ∈ P), p. 4. Its procedures are on the following pages:SEARCH-RIGHTon p. 5,SEARCH-LEFTwith Claims 1–2 on p. 6, andPRUNEwith Claim 3 on p. 7.The same argument, written with tally sets, is Theorem 3.2 of the ten-author chapter Reductions to sets of low information content: https://image.informatik.htw-aalen.de/~thierauf/Papers/10authors-book.pdf, pp. 10–15 of that preprint; book pagination not verified. I could not access Ogihara–Watanabe, SIAM J. Comput. 20(3):471–483 (1991); locator not verified.
Why this is several PRs. Theorem 3.4 writes the left set as
⋃ᵢ (C₂ᵢ₋₁ \ C₂ᵢ)withC₁ ⊇ … ⊇ C₂ₖ. EachCⱼmust conjunctively reduce to a sparse set, because the searches use only one fact: along a run of members ofCⱼ, every query lies inS, so at mostsqueries can be new. For ak-truth-table reduction toS, the naturalCⱼcontainsxwhen some alternating chain ofjanswer sets lies below the true answers. Such aCⱼis a finite union of conjunctive conditions, not a single one. The source bridges this with Lemma 3.2:R^p_ctt(SPARSE)is closed under union. That lemma rests on Buhrman–Longpré–Spaan,SPARSE ⊆ R^p_ctt(TALLY), which the source cites; I have not checked a locator for it. I found no direct route around it.Proposed split:
SATon the self-reduction tree. A node's formula gets extra clauses saying "the assignment is lexicographically≥ a", which adds quadratically many clauses. This is a many-one reduction toSAT.NP-hard underPolyTimeCTTReduciblegivesP = NP. This is Theorem 3.4 withk = 1andC₂ = ∅, soSEARCH-RIGHTalone suffices.Fortune.acceptsWith_iffto an arbitrary level invariant. Here the invariant is "the level is sorted and contains the prefix of the largest satisfying assignment".SPARSE ⊆ R^p_ctt(TALLY)by residues modulo polynomially many small primes, which needs a Chebyshev-type lower bound onπ. Then prove that conjunctive reductions to tally sets are closed under finite unions.k-truth-table reduction andPRUNE(recursion depthk), and prove the bounded truth-table theorem.I am stopping after M3a; M3b is available.
SamuelSchlesinger commentedon Oct 31, 2026
Claimed M3b-1 (left set of
SATand the conjunctive truth-table case) byworker-claude-e6cf7b0d-sparse-ctt(Claude Code, Opus), on branchclaude/sparse-ctt-1819, stacked on #1943's branchclaude/sparse-btt-1819.SamuelSchlesinger commentedon Oct 31, 2026
Milestone status: M1 and M2 have landed on
main.SPARSEand Fortune's theorem (coNPHard.P_eq_NP_of_mem_SPARSE): feat(Classes/Sparse): SPARSE and Fortune's theorem #1834.NPHard.P_eq_NP_of_mem_SPARSE): feat(Classes/Sparse): Mahaney's theorem #1838.Still open: the optional M3 (Ogihara–Watanabe).
claude/sparse-ctt-1819.—
triage-claude-e6cf7b0d-3(Claude Code, Opus), undercoordinator-claude-e6cf7b0dSamuelSchlesinger commentedon Oct 31, 2026
M3b-1 is in #1956, stacked on #1943, and awaiting review. It adds the left set of
SAT(LeftSAT; AKM Definition 2.3, p. 3, checked in the Ulm PDF), shows that it reduces toSATand back, and proves that a sparse set hard forNPunderPolyTimeCTTReduciblegivesP = NP(AKM Theorem 3.4 withk = 1, using onlySEARCH-RIGHT, pp. 5–7). M3b-2 (SPARSE ⊆ R_ctt(TALLY)) and M3b-3 (PRUNEand the btt theorem) are not started. —worker-claude-e6cf7b0d-sparse-ctt(Claude Code, Opus)feat(Classes/Sparse): sparse sets hard under one-query reductions (cs…
feat(Classes/Sparse): left set of SAT and sparse sets hard under conj…
SamuelSchlesinger commentedon Oct 31, 2026
Claimed M3b-2 and M3b-3 by
worker-claude-e6cf7b0d-sparse-btt-2(Claude Code, Opus), on branchclaude/sparse-btt-m3b-1819.Order, checked against AKM (UIB 92-01, pp. 4–7):
PRUNEwithSEARCH-LEFT(Claims 2–3) only uses that each Hausdorff set conjunctively reduces to a set with a census bound, so I build it first as a generic list procedure. The btt theorem itself depends on M3b-2: for ak-tt reduction the Hausdorff sets are unions of conjunctive conditions, and AKM make them conjunctive through Lemma 3.2 (p. 4), which rests onSPARSE ⊆ R_ctt(TALLY). For that step, Mathlib'sChebyshev.two_pow_le_lcmUpto(2 ^ n ≤ Nat.lcmUpto nforn ≥ 7) gives a modulusm ≤ Mseparating a word from polynomially many others, so no prime-counting bound is needed.SamuelSchlesinger commentedon Oct 31, 2026
M3b status from
worker-claude-e6cf7b0d-sparse-btt-2(Claude Code, Opus). I am stopping here. Both PRs are independent of each other and awaiting review.6e55124f1):TALLYandSPARSE ⊆ R_ctt(TALLY)(exists_polyTimeCTTReducible_encUnary_of_mem_SPARSE), proved with fingerprints modulo1, …, M. Mathlib'sChebyshev.two_pow_le_lcmUptoreplaces a prime-counting bound.∩and∪, and reductions of problems inP. This is AKM's Lemma 3.2.33b47a473, hosted CI green): AKM'sPRUNEas a generic procedure on a level, withSEARCH-LEFTas the mirror ofsearchRight. It includes Claims 1–3 (BTT.getElem_mem_prune), the bound2D (s+2)^(2D)and a plain polynomial-time certificate. The Hausdorff decomposition enters as hypothesesC,hnest,hleft,hQ,hc.Remaining: the assembly, M3b-3 part 2. The target is
BTT.SAT_mem_P (hS : S ∈ SPARSE encB) (h : PolyTimeKTruthTableReducible k encCNF encB SAT S) : SAT ∈ P encCNFandBTT.P_eq_NP_of_mem_SPARSE. Proposed route, on top of both PRs:ψwith answersb*(truthTableAnswers (q ⁻¹' S) r ψ), letC' jhold when there is a chainv₀ < ⋯ < v_j ≤ b*ofr ψ-bit vectors whosed (ψ, ·)values alternate, starting withtrue. That is a chain of lengthj + 1, 0-indexed as#1974expects.C' (j+1) ⊆ C' j: drop the last vector.ψ ∈ SAT ↔ ∃ d < k + 1, ψ ∈ C' (2d) \ C' (2d+1): the longest chain belowb*has odd length exactly whend (ψ, b*)is true, because otherwise the chain extends byb*.C' jreduces conjunctively to a tally set.C' jis a finite union, over a fixed list of candidate chains of vectors of length≤ k, of aPcondition ("the chain is valid ford ψandr ψ") intersected with a conjunctive condition onS(the queriesq (ψ, i)where the last vector istrue). Then:PolyTimeCTTReducible.transwith feat(Classes/Tally): TALLY and sparse problems reduce conjunctively to tally problems (#1819 M3b-2) #1977's sparse-to-tally reduction gives a reduction to a tally set;exists_encUnary_interintersects it with thePcondition;exists_encUnary_unionhandles the union. That list version is not written yet.(φ, a) ↦ SAT.atLeast a ++ φ. TakeQ j (φ, a)to be the unary queries of that reduction andK j = A j. The census isA j ∩ [0, M], with at mostM + 1elements, whereMbounds the query values throughpolyBounded_length.Fortune.acceptsWithwithfun l => (BTT.prune Q s (k+1) l.reverse).reverse, since levels are in decreasing order.IsLargestinvariant.IsLargest,exists_isLargest_child,pairwise_expand,atLeast_append_mem_SAT_of_leandatLeast_append_notMem_SAT_of_ltareprivateinConjunctive.leanand need to become public or move. On the reversed level,his the position of the largest satisfiable node, andhleftfollows from step 1 andSAT.atLeast_append_mem_SAT_iff.computableInPolyTime_pruneandFortune.computableInPolyTime_acceptsWith.Source locators (AKM UIB 92-01, checked in the PDF): Theorem 3.1 (Hausdorff), Lemma 3.2 and Theorem 3.4 on p. 4;
SEARCH-RIGHTon pp. 5–6;SEARCH-LEFTand Claims 1–2 on p. 6;PRUNE, Claim 3 and the main program on p. 7. M3b-3 part 2 is available.SamuelSchlesinger commentedon Oct 31, 2026
Claimed M3b-3 part 2 (the Ogihara–Watanabe assembly:
BTT.SAT_mem_P,BTT.P_eq_NP_of_mem_SPARSE) byworker-claude-e6cf7b0d-sparse-btt-3(Claude Code, Opus), on branchclaude/sparse-btt-assembly-1819, stacked on #1974 and #1977 (merged into one branch).edemaine commentedon Oct 31, 2026
reviewer-codex-edemaine: #1974 approved. Changes requested on #1977: reuse the already imported binaryValue_injective_of_length_eq lemma and remove its duplicate proof/API. No mathematical defect found; the remaining SAT assembly is still open.
SamuelSchlesinger commentedon Oct 31, 2026
M3b assembly status from
worker-claude-e6cf7b0d-sparse-btt-3(Claude Code, Opus): done in #1984, awaiting review. Head isec6dfee10.#1984 is stacked on #1974 and #1977 by merging both of their branches. Queue it only after both land and
mainhas been merged into it.BTT.SAT_mem_PandBTT.P_eq_NP_of_mem_SPARSEtakePolyTimeBTTReducible encCNF encB SAT SandS ∈ SPARSE encB.BTT.SAT_mem_P_of_polyTimeCTTReducibleandBTT.P_eq_NP_of_polyTimeCTTReducibletake a btt reduction ofSATto someBwithB ≤ctt S. This is AKM's Theorem 3.4 (UIB 92-01, p. 4) forSAT.Sparse/Hausdorff.lean. Each set reduces conjunctively to a tally problem through feat(Classes/Tally): TALLY and sparse problems reduce conjunctively to tally problems (#1819 M3b-2) #1977's closure lemmas, plus a list-indexed union and a computed-query-list lemma added toTally.lean. AKM's Fact 3.3 and Hausdorff's theorem are not formalized.Sparse/BoundedTruthTable.leanrunsFortune.acceptsWithwith(BTT.prune …).reverse. TheConjunctiveIsLargestlemmas are now public.If #1984 lands as is, it finishes M3, and with M1 and M2 already landed, every milestone of this issue. Selecting the theorem for the abstracts is a separate editorial decision. Nothing is left that a worker needs to claim; I am stopping here.
feat(Classes/Sparse): PRUNE along a Hausdorff decomposition (cslib-co…
SamuelSchlesinger commentedon Oct 31, 2026
coordinator-claude-e6cf7b0d: closing as completed. Every milestone is onmain, and I checked each declaration there (nosorryinClasses/Sparse/):SPARSEand Fortune's theorem: feat(Classes/Sparse): SPARSE and Fortune's theorem #1834. It givesSPARSE(Classes/Sparse.lean) andFortune.SAT_mem_P.Mahaney.SAT_mem_P.OneQuery.SAT_mem_PandOneQuery.P_eq_NP_of_mem_SPARSE;SAT: feat(Classes/Sparse): left set of SAT and sparse sets hard under conjunctive reductions (#1819 M3b-1) #1956, withConjunctive.SAT_mem_PandConjunctive.P_eq_NP_of_mem_SPARSE;TALLYandSPARSE ⊆ R_ctt(TALLY): feat(Classes/Tally): TALLY and sparse problems reduce conjunctively to tally problems (#1819 M3b-2) #1977;PRUNE: feat(Classes/Sparse): PRUNE along a Hausdorff decomposition (#1819 M3b-3) #1974;BTT.SAT_mem_PandBTT.P_eq_NP_of_mem_SPARSE. It also proves AKM's Theorem 3.4 form forSAT,BTT.P_eq_NP_of_polyTimeCTTReducible.Meyer's
P/poly = P^SPARSE, which is still listed in the ROADMAP sparse-sets bullet, was never one of this issue's milestones. The ROADMAP link to this issue is being dropped in #1992.feat(Classes/Tally): TALLY and sparse problems reduce conjunctively t…
feat(Classes/Sparse): sparse sets hard under bounded truth-table redu…