The PL Hierarchy Collapses

DOI10.1137/S0097539795295924zbMATH Open0907.68078OpenAlexW1987889357MaRDI QIDQ4210116FDOQ4210116

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

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

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)

Cited In (4)

• Parameterised counting in logspace
• 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

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)