Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. 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.

We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤m, ≤btt, ≤tt and ≤T and solved the problem for al of them except ≤T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub-Turing reducibilities what were studying in (...) [1, 2]. (shrink)