Theories with self-application and computational complexity.
type: Item
instance of: scholarly article
title: Theories with self-application and computational complexity.
zbMATH Open document ID: 1057.03051
DOI: 10.1016/S0890-5401(03)00086-5
author: Thomas Strahm
published in: Information and Computation
publication date: 2004-03-14T00:00:00Z
review text: 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.
reviewed by: Reinhard Kahle
Mathematics Subject Classification ID: 03F50
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2056068
zbMATH Keywords: explicit mathematics
zbMATH Keywords: bounded applicative theories
zbMATH Keywords: computational complexity
zbMATH Keywords: bounded induction
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: feasible functionals
MaRDI profile type: Publication
cites work: Q3342534
cites work: Q5691043
cites work: Q3679172
cites work: Q3757915
cites work: Higher type recursion, ramification and polynomial time
cites work: A new recursion-theoretic characterization of the polytime functions
cites work: Q3472100
cites work: Q3476809
cites work: Q3794177
cites work: Q4215631
cites work: Q4325772
cites work: Logical frameworks for truth and abstraction. An axiomatic study
cites work: Q4395609
cites work: Feasible Operations and Applicative Theories Based on λη
cites work: Polytime, combinatory logic and positive safe induction
cites work: Q4934292
cites work: Q5586401
cites work: Functional interpretations of feasibly constructive arithmetic
cites work: Q4035304
cites work: Q4133141
cites work: Q4128540
cites work: Q3882452
cites work: Systems of explicit mathematics with non-constructive \(\mu\)-operator. I
cites work: Systems of explicit mathematics with non-constructive \(\mu\)-operator. II
cites work: Generalized recursion theory II. Proceedings of the 1977 Oslo Symposium
cites work: Q3478384
cites work: Q4010354
cites work: Q3138832
cites work: Q3487327
cites work: Q4035308
cites work: Q3773876
cites work: Systems of explicit mathematics with non-constructive \(\mu\)-operator and join
cites work: Q5286672
cites work: Q4722037
cites work: On characterizations of the basic feasible functionals. I
cites work: A well-ordering proof for Feferman's theoryT 0
cites work: Q4941991
cites work: Totality in applicative theories
cites work: Some theories with positive induction of ordinal strength φω0
cites work: A new Characterization of Type-2 Feasibility
cites work: Q4856172
cites work: A foundational delineation of poly-time
cites work: Q4501154
cites work: Q4850553
cites work: The \(\mu\) quantification operator in explicit mathematics with universes and iterated fixed point theories with ordinals
cites work: Polynomial and abstract subrecursive classes
cites work: Q5600870
cites work: Q4218943
cites work: Classes of Predictably Computable Functions
cites work: Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
cites work: Fragments of arithmetic
cites work: Herbrand analyses
cites work: A proof-theoretic characterization of the basic feasible functionals
cites work: Polynomial time operations in explicit mathematics
cites work: The non-constructive \(\mu\) operator, fixed point theories with ordinals, and the bar rule
cites work: A second order version of S2i and U21
cites work: Subrecursiveness: Machine-independent notions of computability in restricted time and storage
cites work: Constructivism in mathematics. An introduction. Volume I

Theories with self-application and computational complexity. (cites work)
cites work: Notes on polynomially bounded arithmetic

Theories with self-application and computational complexity. (full work available at URL)
full work available at URL: s0890-5401(03)00086-5

Theories with self-application and computational complexity. (OpenAlex ID)
OpenAlex ID: W1966026587