scientific article

zbMATH Open0757.03021MaRDI QIDQ4010352FDOQ4010352

Stephen Cook

Publication date: 27 September 1992

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

Recommendations

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

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)

Cited In (41)

• Speed-up theorems in type-2 computations using oracle Turing machines
• Title not available (Why is that?)
• Type-two polynomial-time and restricted lookahead
• Functional interpretations of feasibly constructive arithmetic
• Title not available (Why is that?)
• Parametrised second-order complexity theory with applications to the study of interval computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• An arithmetic for polynomial-time computation
• Title not available (Why is that?)
• Computational Complexity Via Finite Types
• Title not available (Why is that?)
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• A new recursion-theoretic characterization of the polytime functions
• Higher order interpretation for higher order complexity
• Higher type recursion, ramification and polynomial time
• Title not available (Why is that?)
• An abstract data type for real numbers
• Title not available (Why is that?)
• 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
• \({\mathcal M}^\omega\) considered as a programming language
• Title not available (Why is that?)
• Safe Weak Minimization Revisited
• Towards the computational complexity of \(\mathcal{PR}^ \omega\)-terms
• Functions computable with limited access to NP
• Title not available (Why is that?)
• Feasible functionals and intersection of ramified types
• Complexity for type-2 relations
• On a complexity-based way of constructivizing the recursive functions
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Type 2 computational complexity of functions on Cantor's space
• Title not available (Why is that?)

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)