Recursion-Theoretic Alternation

We introduce four recursion schemes, which, operating on a tree-like data structure, capture different models of computation based on alternating bounded quantifiers. By encoding inputs as paths, we recover and expand characterizations of complexity classes between deterministic linear time and polynomial space; by encoding them as balanced trees, we recover characterizations of alternating logarithmic time and polylogarithmic space. We propose recursion-theoretic characterizations of logarithmic and polylogarithmic time, as defined via Turing machines with random access to the input, and show that the classes of functions obtained capture, at least, the desired classes, and, at most, their alternating versions. Should the proposed characterizations be precise, we show that characterizations of linear and polynomially bounded alternating classes can be adapted to alternating classes with logarithmic and polylogarithmic resource bounds, simply by changing the way in which inputs are encoded. We discuss how, from these characterizations, some open problems in complexity theory can be obtained from known results by making alterations to recursion schemes.