The PL Hierarchy Collapses

DOI10.1137/S0097539795295924MaRDI QIDQ4210116zbMATH OpenOpenAlexFDO

Authors Ogihara, Mitsunori

Publication date 21 September 1998

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

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

zbMATH Keywords

constant-depth circuitsrelativizationprobabilistic complexity classesnondeterministic complexity classeslogspace reducibility

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1256722
• The strong exponential hierarchy collapses
• A Downward Collapse within the Polynomial Hierarchy
• scientific article; zbMATH DE number 4080916
• The collapse of the bounded width hierarchy
• Collapse
• Gemmating P systems: Collapsing hierarchies.
• On collapsing the polynomial-time hierarchy
• The additive collapse

Cited in

(4)

• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
• Isolation, matching, and counting uniform and nonuniform upper bounds
• A note on closure properties of logspace MOD classes
• Parameterised counting in logspace

This page was built for publication: The PL Hierarchy Collapses

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