Theories with self-application and computational complexity. (Q1427856): Difference between revisions

The author gives a very elegant and uniform characterization of various complexity classes -- namely FPtime, FPtimeLinspace, FPspace, and FLinspace -- in the context of Feferman's explicit mathematics [``Constructive theories of functions and classes'', Logic colloquium '78, Stud. Logic Found. Math. 97, 159--224 (1979; Zbl 0441.03022)]. It makes use of the function algebra characterization of these classes [cf., e.g., \textit{P. Clote}, ``Computation models and function algebras'', in: E. Griffor (ed.), Handbook of computability theory, Stud. Logic Found. Math. 140, 589--681 (1999; Zbl 0942.68049)], but tailors the classes by specific forms of bounded induction principles. The approach is extended to the full polynomial-time hierarchy by adding a type-two function for bounded quantification.