Provably total functions of intuitionistic bounded arithmetic

DOI10.2307/2275282zbMATH Open0778.03019OpenAlexW1987943786MaRDI QIDQ4032632FDOQ4032632

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

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

zbMATH Keywords

computabilitycomplexity classes of functions in fragments of intuitionistic bounded arithmetic

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Cites Work

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

Cited In (15)

• Provably recursive functions of constructive and relatively constructive theories
• Feasible functions over co-inductive data
• Functional interpretations of feasibly constructive arithmetic
• 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
• Title not available (Why is that?)
• An Independence Result for Intuitionistic Bounded Arithmetic
• A tight relationship between generic oracles and type-2 complexity theory
• Title not available (Why is that?)
• Effectiveness and provability
• On parallel hierarchies and \(R_k^i\)

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)