The PL Hierarchy Collapses
From MaRDI portal
Publication:4210116
DOI10.1137/S0097539795295924zbMath0907.68078OpenAlexW1987889357MaRDI QIDQ4210116
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
probabilistic complexity classesrelativizationconstant-depth circuitsnondeterministic complexity classeslogspace reducibility
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Parameterised counting in logspace ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) ⋮ A note on closure properties of logspace MOD classes