scientific article

zbMath0757.03021MaRDI QIDQ4010352

Stephen A. Cook

Publication date: 27 September 1992

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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)

Related Items (15)

Towards the computational complexity of \(\mathcal{PR}^ \omega\)-terms ⋮ Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals ⋮ Computation models and function algebras ⋮ Type 2 polynomial hierarchies ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ An abstract data type for real numbers ⋮ Type-two polynomial-time and restricted lookahead ⋮ Functional interpretations of feasibly constructive arithmetic ⋮ A new recursion-theoretic characterization of the polytime functions ⋮ An arithmetic for polynomial-time computation ⋮ Unnamed Item ⋮ Parametrised second-order complexity theory with applications to the study of interval computation ⋮ Speed-up theorems in type-2 computations using oracle Turing machines ⋮ Feasible functionals and intersection of ramified types ⋮ \({\mathcal M}^\omega\) considered as a programming language

This page was built for publication: