Double-exponential inseparability of Robinson subsystem Q+
From MaRDI portal
Publication:3083130
DOI10.2178/jsl/1294170991zbMath1222.03033MaRDI QIDQ3083130
Giovanni Faglia, Lavinia Egidi
Publication date: 18 March 2011
Published in: The Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/jsl/1294170991
additive fragment of Robinson's system \(Q\); double exponential time inseparability; finitely axiomatizable first-order theory; theory of addition
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03C07: Basic properties of first-order languages and structures
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A uniform method for proving lower bounds on the computational complexity of logical theories
- The complexity of logical theories
- A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
- The computational complexity of logical theories
- Classifying the computational complexity of problems
- A Decision Procedure for the First Order Theory of Real Addition with Order