scientific article; zbMATH DE number 4006252

zbMATH Open0621.03026MaRDI QIDQ3757904FDOQ3757904

Peter Clote, Gaisi Takeuti

Publication date: 1986

Title of this publication is not available (Why is that?)

Recommendations

• scientific article
• 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

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)

Cited In (12)

• Notations for exponentiation.
• Functional interpretations of feasibly constructive arithmetic
• Title not available (Why is that?)
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computation models and function algebras
• The strong exponential hierarchy collapses
• Diophantine induction
• Tight bounds on expected time to add correctly and add mostly correctly
• Computing in Finite Time

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)