Theories with self-application and computational complexity.

DOI10.1016/S0890-5401(03)00086-5zbMath1057.03051OpenAlexW1966026587MaRDI QIDQ1427856

Thomas Strahm

Publication date: 14 March 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00086-5

zbMATH Keywords

computational complexitybounded arithmeticexplicit mathematicsbounded inductionbounded applicative theoriesfeasible functionals

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Metamathematics of constructive systems (03F50)

Related Items (11)

A feasible theory of truth over combinatory algebra ⋮ The provably terminating operations of the subsystem PETJ of explicit mathematics ⋮ A new model construction by making a detour via intuitionistic theories. I: Operational set theory without choice is \(\Pi_1\)-equivalent to KP ⋮ Primitive recursive selection functions for existential assertions over abstract algebras ⋮ About Truth and Types ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Elementary explicit types and polynomial time operations ⋮ Realisability in weak systems of explicit mathematics ⋮ Remarks on applicative theories ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ Applicative theories for logarithmic complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Functional interpretations of feasibly constructive arithmetic
• A proof-theoretic characterization of the basic feasible functionals
• Fragments of arithmetic
• Generalized recursion theory II. Proceedings of the 1977 Oslo Symposium
• Constructivism in mathematics. An introduction. Volume I
• A new recursion-theoretic characterization of the polytime functions
• Polynomial and abstract subrecursive classes
• The \(\mu\) quantification operator in explicit mathematics with universes and iterated fixed point theories with ordinals
• Systems of explicit mathematics with non-constructive \(\mu\)-operator. I
• A foundational delineation of poly-time
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• Polytime, combinatory logic and positive safe induction
• Higher type recursion, ramification and polynomial time
• The non-constructive \(\mu\) operator, fixed point theories with ordinals, and the bar rule
• Totality in applicative theories
• Systems of explicit mathematics with non-constructive \(\mu\)-operator. II
• Logical frameworks for truth and abstraction. An axiomatic study
• Systems of explicit mathematics with non-constructive \(\mu\)-operator and join
• Herbrand analyses
• On characterizations of the basic feasible functionals, Part I
• Classes of Predictably Computable Functions
• A second order version of S₂ⁱ and U₂¹
• Polynomial time operations in explicit mathematics
• Feasible Operations and Applicative Theories Based on λη
• A well-ordering proof for Feferman's theoryT 0
• A new Characterization of Type-2 Feasibility
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage
• Some theories with positive induction of ordinal strength φω0
• Notes on polynomially bounded arithmetic

This page was built for publication: Theories with self-application and computational complexity.