Alphabeta Math
False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12
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.

FALSE: every PP algorithm has bounded error separated from one half by a fixed constant

Statement

Every PP algorithm has bounded error separated from one half by a fixed constant.

Facts & Assumptions

Given: the class PP.

[L1]

A PP machine need only accept yes-instances with probability strictly greater than 1/2 and no-instances with probability at most 1/2 (The classes RP, coRP, ZPP, BPP, and PP).

Refutation

technique · direct
1.1L1givenconstruct

Let A:={x∈{0,1}∗:x begins with 1}. Its deterministic membership test D(x) is computable in linear time. Consider the probabilistic machine that uses one fair bit b and an independent string r∈{0,1}n+1, accepts when D(x)=1 and either b=1 or r=0n+1, and accepts when D(x)=0 exactly if b=1 and r≠0n+1. Then yes-instances are accepted with probability 1/2+2−(n+2), while no-instances are accepted with probability 1/2−2−(n+2).

2.1L1step 1.1algebra∎

Step 1.1 still satisfies the PP threshold condition [L1], but the gap from 1/2 shrinks with n and is not bounded below by any fixed positive constant. So the statement is false.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

2 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