On existence of complete sets for bounded reducibilities
Valeriy K. Bulitko, Vadim Bulitko · Mathematical logic quarterly · 2003
Abstract Classical reducibilities have complete setsUthat any recursively enumerable set can be reduced toU. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)