Double-exponential inseparability of Robinson subsystem Q+

DOI10.2178/jsl/1294170991zbMath1222.03033OpenAlexW1978499509MaRDI 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

zbMATH Keywords

additive fragment of Robinson's system \(Q\)double exponential time inseparabilityfinitely axiomatizable first-order theorytheory of addition

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Basic properties of first-order languages and structures (03C07)

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

This page was built for publication: Double-exponential inseparability of Robinson subsystem Q₊