Provably total functions of intuitionistic bounded arithmetic

DOI10.2307/2275282MaRDI QIDQ4032632zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 440477
• scientific article; zbMATH DE number 4066875
• Intuitionistic formal theories with realizability in subrecursive classes
• Extracting Algorithms from Intuitionistic Proofs
• Two General Results on Intuitionistic Bounded Theories

Cites work

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

Cited in

(16)

• Provably recursive functions of constructive and relatively constructive theories
• Functional interpretations of feasibly constructive arithmetic
• Feasible functions over co-inductive data
• Mining the surface: witnessing the low complexity theorems of arithmetic
• Preservation theorems for bounded formulas
• An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras
• Classifying the Provably Total Functions of PA
• Computation models and function algebras
• Type 2 polynomial hierarchies
• scientific article; zbMATH DE number 7324257 (Why is no real title available?)
• A tight relationship between generic oracles and type-2 complexity theory
• An Independence Result for Intuitionistic Bounded Arithmetic
• scientific article; zbMATH DE number 440477 (Why is no real title available?)
• On the unprovability of circuit size bounds in intuitionistic \(\mathsf{S}^1_2\)
• On parallel hierarchies and R_k^i
• Effectiveness and provability

This page was built for publication: Provably total functions of intuitionistic bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032632)