Alphabeta MathHow 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: Savitch's algorithm stores the whole configuration graph
Statement
Savitch's algorithm stores the whole configuration graph.
Facts & Assumptions
Given: Savitch's recursive reachability procedure.
The recursive definition reduces one reachability query to two shorter subqueries through one midpoint candidate at a time (The bounded reachability recursion for directed paths of length at most 2^i).
A direct implementation keeps only the current endpoints, the current midpoint candidate, and the recursion stack, so the full search uses only space on an -vertex graph (The bounded reachability recursion uses logarithmic recursion depth).
Refutation
By [L1], Savitch's recursion examines one midpoint candidate and one shorter subproblem at a time, rather than materializing all candidates or all adjacency data at once.
By [L2], the whole recursion uses only polylogarithmic space in the number of configurations. An explicit storage of the whole configuration graph would require at least enough space to name all of its vertices, which is much larger than that bound in general. So the statement is false.
Depends on
Used by
Dependency tree · two levels
4 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
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
- Eric Blais, Models of Computation, 17. Space Complexity (standard reference, not scraped)