Space Bounded Computation
Space as a counted resource, and space-time trade-offs for circuit evaluation and satisfiability.
| Status | Statement | Tags |
|---|---|---|
|
CSAT with Small Space and Preprocessing Conjecture 1.2 of the source, a parameterized family rather than a single claim. Corollary 1.3 turns each parameter setting into a limitation on succinct IOPs. The source attaches decreasing confidence as the class T grows, calling the largest setting only (arguably) unlikely to be false rather than confidently believed. 4 open |
Interactive Oracle ProofsProof Size Lower BoundsSpace Bounded ComputationTime Space Tradeoffslower-boundbarrier (ai) |
No matching items