Provably total functions of intuitionistic bounded arithmetic

DOI10.2307/2275282zbMath0778.03019OpenAlexW1987943786MaRDI QIDQ4032632

Victor Harnik

Publication date: 1 April 1993

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275282

zbMATH Keywords

computabilitycomplexity classes of functions in fragments of intuitionistic bounded arithmetic

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Related Items

A tight relationship between generic oracles and type-2 complexity theory ⋮ Preservation theorems for bounded formulas ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Computation models and function algebras ⋮ Type 2 polynomial hierarchies ⋮ An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras ⋮ Functional interpretations of feasibly constructive arithmetic ⋮ Provably recursive functions of constructive and relatively constructive theories

Cites Work

• Bounded arithmetic and the polynomial hierarchy
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES