scientific article; zbMATH DE number 4006252
computable functionscut free Gentzen proofsdeterministic timeexponential timeKalmar elementarymany-sorted arithmeticnon-deterministic timenormalized formal proofsnumber-theoretic functionpolynomial timeprovably recursive
Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Hierarchies of computability and definability (03D55) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Higher-type and set recursion theory (03D65) Complexity of proofs (03F20) Analysis of algorithms and problem complexity (68Q25)
- Bounded arithmetic for NC, ALogTIME, L and NL
- A new recursion-theoretic characterization of the polytime functions
- Tight bounds on expected time to add correctly and add mostly correctly
- Notations for exponentiation.
- Computing in Finite Time
- scientific article; zbMATH DE number 4160708 (Why is no real title available?)
- scientific article; zbMATH DE number 67686 (Why is no real title available?)
- A model theoretic proof of a subexponential time witnessing theorem
- scientific article; zbMATH DE number 1354146 (Why is no real title available?)
- The strong exponential hierarchy collapses
- Diophantine induction
- Computation models and function algebras
- Functional interpretations of feasibly constructive arithmetic
- Numeral completeness of weak theories of arithmetic
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3757904)
