Alphabeta Math
ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 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.

An alternating machine for a quantified Boolean formula

Example

For the formula

Φ:=∃x ∀y (x∨y),

the existential player has a winning strategy, and the corresponding alternating machine accepts by choosing x=1 at its first existential state.

Facts & Assumptions

Given: the formula Φ=∃x ∀y (x∨y).

[L1]

The quantified formula game lets the existential player choose existential variables and the universal player choose universal variables (The quantified formula game for a quantified Boolean formula).

[L2]

Truth of the formula is equivalent to existence of a winning strategy for the existential player (A quantified Boolean formula is true if and only if the existential player has a winning strategy in its game).

[L3]

AP equals PSPACE, and the AP side is realized by alternating choices along the quantifier prefix (AP equals PSPACE).

Verification

technique · direct
1.1L1given

In the game of [L1], if Player E chooses x=1 on the first move, then the matrix x∨y is true regardless of whether Player A later chooses y=0 or y=1. So Player E has a winning strategy.

2.1L2L3step 1.1

By [L2], step 1.1 implies that Φ is true. The corresponding alternating machine from [L3] uses an existential state to choose x and a universal state to branch over the two values of y; after the choice x=1, both universal branches accept.

3.1L3step 2.1∎

This is the smallest nontrivial picture behind the inclusion PSPACE⊆AP in AP equals PSPACE.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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