Lower bounds for the low hierarchy

DOI10.1145/147508.147546zbMath0799.68081OpenAlexW2050774914MaRDI QIDQ4302826

Hemaspaandra, Lane A., Eric W. Allender

Publication date: 21 August 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1802/5465

zbMATH Keywords

lower boundssparse setslow hierarchy

Mathematics Subject Classification ID

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

Related Items

A complexity theory for feasible closure properties, Locating \(P\)/poly optimally in the extended low hierarchy, Self-reducible sets of small density, A refinement of the low and high hierarchies, The extended low hierarchy is an infinite hierarchy, The join can lower complexity, Upper bounds for the complexity of sparse and tally descriptions, Fault-tolerance and complexity (Extended abstract), A note on P-selective sets and closeness, Structural properties of oracle classes, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, The structure of logarithmic advice complexity classes, Boolean operations, joins, and the extended low hierarchy