Space complexity vs. query complexity
From MaRDI portal
Publication:937195
DOI10.1007/s00037-008-0239-zzbMath1149.68032OpenAlexW2026717573MaRDI QIDQ937195
Asaf Shapira, Oded Lachish, Ilan Newman
Publication date: 20 August 2008
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.5992
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Hierarchy theorems for property testing ⋮ Hierarchy Theorems for Property Testing ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ A combinatorial characterization of smooth LTCs and applications