Lowness Properties of Sets in the Exponential-Time Hierarchy

DOI10.1137/0217030zbMath0652.68059OpenAlexW2054394744MaRDI QIDQ3798242

Pekka Orponen, David A. Russo, Ronald V. Book, Osamu Watanabe

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217030

zbMATH Keywords

polynomial-time hierarchysparse setpolynomial lownessexponential lownesssmall generalized Kolmogorov complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

On relativizations with restricted number of accesses to the oracle set ⋮ Polylog depth, highness and lowness for E

This page was built for publication: Lowness Properties of Sets in the Exponential-Time Hierarchy