Index sets and presentations of complexity classes

AbstractThis paper draws close connections between the ease of presenting a given complexity class b and the position of the index sets Ib = [lcub]i : L(Mi) ϵ b[rcub] and Jb = [lcub]i : Miis total ΛL(Mi) ∉ b[rcub] in the arithmetical hierarchy. For virtually all classes b studied in the literature, the lowest levels attainable are Ib ϵ ∑03 and Jb ϵ Π02; the first holds iff b is Δ02-presentable, and the second iff b is recursively presentable. A general kind of priority argument is formulated, and it is shown that every property enforcible by it is not recursively presentable. It follows that the classes of P-immune and P-biimmune languages in exponential time are not recursively presentable. It is shown that for all b with Ib ∉ ∑03, “many” members of b do not provably (in true Π2-arithmetic) belong to b. A class H is exhibited such that IH ϵ ∑03 is open, and IH ∉ ∑03 implies that the polynomial hierarchy is infinite