Space hierarchy results for randomized and other semantic models

DOI10.1007/S00037-009-0277-1zbMath1213.68299OpenAlexW2028390094MaRDI QIDQ626680

Dieter van Melkebeek, Jeff Kinne

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0277-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On derandomization and average-case complexity of monotone functions ⋮ Catalytic space: non-determinism and hierarchy

This page was built for publication: Space hierarchy results for randomized and other semantic models