scientific article; zbMATH DE number 4006252

MaRDI QIDQ3757904zbMATHFDO

Authors Peter Clote, Gaisi Takeuti

Publication date 1986

zbMATH Keywords

polynomial timedeterministic timeexponential timecomputable functionsnumber-theoretic functioncut free Gentzen proofsKalmar elementarymany-sorted arithmeticnon-deterministic timenormalized formal proofsprovably recursive

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hierarchies of computability and definability (03D55) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Higher-type and set recursion theory (03D65)

Recommendations

• scientific article; zbMATH DE number 4059391
• Characterising polynomial time computable functions using theories with weak set existence principles
• scientific article; zbMATH DE number 440477
• Exponentiation and second-order bounded arithmetic
• Publication:3487327

Cited in

(12)

• scientific article; zbMATH DE number 1354146 (Why is no real title available?)
• Computation models and function algebras
• Bounded arithmetic for NC, ALogTIME, L and NL
• scientific article; zbMATH DE number 4160708 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Notations for exponentiation.
• Diophantine induction
• The strong exponential hierarchy collapses
• Computing in Finite Time
• scientific article; zbMATH DE number 67686 (Why is no real title available?)
• Tight bounds on expected time to add correctly and add mostly correctly
• Functional interpretations of feasibly constructive 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)