Two refinements of the polynomial hierarchy

DOI10.1007/3-540-57785-8_161MaRDI QIDQ4942622zbMATH OpenFDO

Authors Victor Selivanov

Publication date 16 March 2000

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

Full work available at URL https://doi.org/10.1007/3-540-57785-8_161

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited in

(11)

• Fine hierarchy of regular \(\omega\)-languages
• A reducibility for the dot-depth hierarchy
• A note on parallel queries and the symmetric-difference hierarchy.
• The Shrinking Property for NP and coNP
• Fine hierarchies via Priestley duality
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• Query order in the polynomial hierarchy
• Fine hierarchy of regular -languages
• On the main scientific achievements of Victor Selivanov
• The shrinking property for NP and coNP
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: Two refinements of the polynomial hierarchy

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