Logical characterizations of bounded query classes. I: Logspace oracle machines

DOI10.1007/BFB0023899MaRDI QIDQ2757847zbMATH OpenFDO

Authors Iain Stewart

Publication date 4 December 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0023899

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 223336
• Oracles and quantifiers
• scientific article; zbMATH DE number 515747
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
• scientific article; zbMATH DE number 223337

Cited in

(9)

• Characterizing small depth and small space classes by operators of higher types
• scientific article; zbMATH DE number 515747 (Why is no real title available?)
• Logical Description of Monotone NP Problems
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
• Relativization of Gurevich’s Conjectures
• scientific article; zbMATH DE number 223336 (Why is no real title available?)
• scientific article; zbMATH DE number 223337 (Why is no real title available?)
• From almost optimal algorithms to logics for complexity classes via listings and a halting problem
• Methods for proving completeness via logical reductions

This page was built for publication: Logical characterizations of bounded query classes. I: Logspace oracle machines

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