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

DOI10.1016/0304-3975(80)90036-5MaRDI QIDQ1155607zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• A Decision Procedure for the First Order Theory of Real Addition with Order
• scientific article; zbMATH DE number 3685448 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 7526291 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On restricted turing computability
• Separating Nondeterministic Time Complexity Classes
• Techniques for separating space complexity classes
• The complexity of logical theories
• The computational complexity of logical theories
• The polynomial-time hierarchy

Cited in

(10)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1155607)