INDEX SETS AND PRESENTATIONS OF COMPLEXITY CLASSES

This paper draws close connections between the ease of presenting a gi ven complexity class C and the position of the index sets I-C = {i : L (M(i)) is an element of C} and J(C) = {i : M(i) is total boolean AND L (M(i)) is not an element of C} in the arithmetical hierarchy. For virt ually all classes C studied in the literature, the lowest levels attai nable are I-C is an element of Sigma(3)(0) and J(c) is an element of P i(2)(0); the first holds iff C is Delta(2)(0)-presentable, and the sec ond iff C is recursively presentable. A general kind of priority argum ent is formulated, and it is shown that every property enforcible by i t is not recursively presentable. It follows that the classes of P-imm une and P-biimmune languages in exponential time are not recursively p resentable. It is shown that for all C with I-C is not an element of S igma(3)(0), ''many'' members of C do not provably (in true Pi(2)-arith metic) belong to C. A class H is exhibited such that I-H is an element of Sigma(3)(0) is open, and I-H is not an element of Sigma(3)(0) impl ies that the polynomial hierarchy is infinite.