Super-Exponential Complexity of Presburger Arithmetic¶
Fischer, M. J., & Rabin, M. O. (1974). Super-Exponential Complexity of Presburger Arithmetic. Complexity of Computation.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Mechanisms¶
- Language-Fragment Restriction
- Cut the fragment too tight and the very thing users need is missing, so they abandon it for an undecidable escape hatch; and decidability is not feasibility
This sourceProves enormous lower bounds for decidable theories such as Presburger arithmetic, showing that guaranteed decidability can remain computationally infeasible.
- Cut the fragment too tight and the very thing users need is missing, so they abandon it for an undecidable escape hatch; and decidability is not feasibility
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:dda266d2cbb0 · see in the full table