Alphabeta Math
DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-generatedjudge pass (gpt-6-sol)audited 2026-09-30
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.

PCP classes with completeness and soundness

Definition

Let r,q:N→N be resource bounds and let 0≤s<c≤1 be constants independent of input length. A language K⊆{0,1}∗ belongs to PCP⁡(r,q;c,s) exactly when there are a verifier V of the type in PCP verifier resources and deterministic proof strings, with randomness bound r(n) and query bound q(n), a fixed finite proof alphabet, and a polynomial p such that its addressable proof length LV(n) is at most p(n) and the following hold for every input x of length n:

  • If x∈K, there is one fixed proof π with Pr⁡[Vπ(x) accepts]≥c.
  • If x∉K, every fixed proof π satisfies Pr⁡[Vπ(x) accepts]≤s.

Both probabilities are over the verifier's coins; the same deterministic proof is used for every coin string. In the shorthand PCP⁡(log⁡n,O(1)), the proof alphabet is {0,1}, the randomness is O(log⁡n), the number of bit queries is bounded by a constant, completeness is perfect (c=1), and soundness is at most some fixed constant s<1. Here O(1) means a constant query bound, not exactly one query.

Depends on

Used by

Dependency tree · two levels

3 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