Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

DOI10.1137/0220025zbMATH Open0798.03044OpenAlexW4255515059MaRDI QIDQ3971675FDOQ3971675

Authors: Jim Kadin 

Publication date: 25 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220025

zbMATH Keywords

collapsecomplexity hierarchiesparallel query hierarchy

Mathematics Subject Classification ID

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

Cited In (2)

• Exact complexity of exact-four-colorability
• The complexity of online manipulation of sequential elections

This page was built for publication: Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

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