On time-space classes and their relation to the theory of real addition

DOI10.1016/0304-3975(80)90036-5zbMath0467.03038OpenAlexW1965844655MaRDI QIDQ1155607

Anna R. Bruss, Albert R. Meyer

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90036-5

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

SAFE RECURSIVE SET FUNCTIONS, The complexity of query evaluation in indefinite temporal constraint databases, Classifying the computational complexity of problems, The complexity of logical theories, A uniform method for proving lower bounds on the computational complexity of logical theories, Interactive proof systems and alternating time-space complexity, Towards separating nondeterminism from determinism, Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories, Real addition and the polynomial hierarchy, Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Cites Work

• The complexity of logical theories
• Techniques for separating space complexity classes
• The polynomial-time hierarchy
• The computational complexity of logical theories
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Separating Nondeterministic Time Complexity Classes
• On restricted turing computability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item