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(φ)>2n1, 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.1

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.

L1given
1.2

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

L2L3givenconstructalgebra
2.1

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.

L1step 1.1step 1.2

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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