Alphabeta Math
CorollaryStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

MajoritySAT is PP-complete

Statement

MajoritySAT is PP-complete under polynomial-time many-one reductions.

Facts & Assumptions

Given: the declared-variable convention for formulas.

[L1]

MajoritySAT uses the strict threshold NumberSAT(φ)>2n−1, including its n=0 interpretation, by MajoritySAT.

[L2]

PP is strict sign testing for GapP, by PP is strict sign testing for Gap-P.

[L3]

Cook--Levin can preserve accepting paths exactly, by The Cook--Levin construction can be made parsimonious.

Proof

technique · direct
1.1L1given

On a well-formed formula with n declared variables, a probabilistic machine chooses the n assignment bits uniformly and accepts exactly on a satisfying assignment. Its acceptance probability is NumberSAT(φ)/2n, so [L1] gives membership in PP; for n=0 the unique random string is the empty assignment.

1.2L2L3givenconstructalgebra

For hardness, normalize a PP machine to 2p paths with p≥1, a of them accepting. By [L3] obtain a formula φ with exactly a satisfying assignments. Add uniquely forced variables until its declared count q obeys q≥p, preserving its count. For u=(uq−1,…,u0) let T(u)=uq−1∨⋯∨up−1; exactly 2q−2p−1 assignments satisfy T. With a fresh selector z, put θ=(¬z∧φ)∨(z∧T). Then #θ=a+2q−2p−1>2q  ⟺  a>2p−1. The formula and its declared list are produced in polynomial time.

2.1L1step 1.1step 1.2∎

Step 1.2 is a membership-preserving reduction from every PP language to MajoritySAT, and step 1.1 gives membership; hence MajoritySAT is PP-complete.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources