scientific article; zbMATH DE number 65741

MaRDI QIDQ4010352zbMATH OpenFDO

Authors Stephen Cook

Publication date 27 September 1992

zbMATH Keywords

polynomial-time computabilityhigher-type computabilitycomplexity theory of higher-type functionalspolynomial-time functionals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Higher-type and set recursion theory (03D65)

Recommendations

• scientific article; zbMATH DE number 2110623
• Some applications of logic to feasibility in higher types
• scientific article; zbMATH DE number 66471
• scientific article; zbMATH DE number 2204752
• scientific article; zbMATH DE number 517086

Cited in

(45)

• Speed-up theorems in type-2 computations using oracle Turing machines
• Functional interpretations of feasibly constructive arithmetic
• scientific article; zbMATH DE number 1948174 (Why is no real title available?)
• A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
• scientific article; zbMATH DE number 5885061 (Why is no real title available?)
• Parametrised second-order complexity theory with applications to the study of interval computation
• Declassification policy for program complexity analysis
• scientific article; zbMATH DE number 4112573 (Why is no real title available?)
• An arithmetic for polynomial-time computation
• Complete and tractable machine-independent characterizations of second-order polytime
• scientific article; zbMATH DE number 2110623 (Why is no real title available?)
• Computational Complexity Via Finite Types
• scientific article; zbMATH DE number 1390026 (Why is no real title available?)
• scientific article; zbMATH DE number 2204752 (Why is no real title available?)
• The basic feasible functionals in computable analysis
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• A new recursion-theoretic characterization of the polytime functions
• A tier-based typed programming language characterizing feasible functionals
• Computing with Functionals—Computability Theory or Computer Science?
• Higher order interpretation for higher order complexity
• Higher type recursion, ramification and polynomial time
• scientific article; zbMATH DE number 3933051 (Why is no real title available?)
• An abstract data type for real numbers
• \({\mathcal M}^\omega\) considered as a programming language
• scientific article; zbMATH DE number 517086 (Why is no real title available?)
• Complete and tractable machine-independent characterizations of second-order polytime
• Computation models and function algebras
• Type 2 polynomial hierarchies
• Computability and the Implicit Function Theorem
• scientific article; zbMATH DE number 4087654 (Why is no real title available?)
• Safe Weak Minimization Revisited
• Towards the computational complexity of \(\mathcal{PR}^ \omega\)-terms
• Functions computable with limited access to NP
• scientific article; zbMATH DE number 1735623 (Why is no real title available?)
• Complexity for type-2 relations
• On a complexity-based way of constructivizing the recursive functions
• Feasible functionals and intersection of ramified types
• The complexity types of computable sets
• Theories with self-application and computational complexity.
• On the computational complexity of Longley's \(H\) functional
• On functional complexity and superpositions of functions
• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• Type 2 computational complexity of functions on Cantor's space
• scientific article; zbMATH DE number 66471 (Why is no real title available?)
• scientific article; zbMATH DE number 1870418 (Why is no real title available?)

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