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 (10)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On time-space classes and their relation to the theory of real addition