Complexity for type-$2$ relations.
Mike Townsend · Notre Dame Journal of Formal Logic · 1990
If Σ is an alphabet, then a type-2 functional is a (partial) function whose arguments are elements of Σ* and functions from Σ* into Σ*.Type-2 relations are the domains of such functionals.We consider the natural extension, POLY, of the class of polynomial time functions to include type-2 functionals, and a variant, POLY, in which the time bounds depend only on the string arguments.Using these, we define two possible extensions of the (relativized) polynomial hierarchy to include type-2 relations.For example, Σξ = Tίξ is the class of relations whose characteristic functionals are in POLY.Then Σ£ +1 is the class of relations definable by POLY length bounded existential quantification of relations in Π£, and dually for Π^+ 1 .Thus Σf is the type-2 analogue of NP.For any function g, we may relativize the definitions of Σζ (Π£) to obtain Σj* (Π£*).Let Σζ denote |J Σ% g .g Some properties of the (relativized) hierarchy are studied.A similar analysis is carried out for the hierarchy based on POLY.In addition, we consider some topological notions that seem 'naturally' associated with time and space bounded computations of oracle Turing machines, and we give topological characterizations of several classes of type-2 relations.In particular, we give a topological characterization of Σf.We use these characterizations to examine analogues of several well-known open questions of computational complexity theory.For example, we show that a certain type-2 analogue of the NP = PSPACE question has a negative answer.These results suggest that topological considerations are an integral part of the study of resource bounded computations of oracle Turing machines.*I would like to thank