A new Characterization of Type-2 Feasibility

DOI10.1137/S0097539794263452zbMath0843.68028MaRDI QIDQ4875448

Bruce M. Kapron, Stephen A. Cook

Publication date: 5 June 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

oracle Turing machinetype-2 functionalspolynomial-time-computable operators

Mathematics Subject Classification ID

Related Items (25)

On the Versatility of Open Logical Relations ⋮ Exact real computation of solution operators for linear analytic systems of partial differential equations ⋮ Towards Computational Complexity Theory on Advanced Function Spaces in Analysis ⋮ Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals ⋮ The basic feasible functionals in computable analysis ⋮ Game semantics approach to higher-order complexity ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ Unnamed Item ⋮ Feasible Iteration of Feasible Learning Functionals ⋮ Theories with self-application and computational complexity. ⋮ Quantitative continuity and Computable Analysis in Coq ⋮ Type-two polynomial-time and restricted lookahead ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Unnamed Item ⋮ Parametrised second-order complexity theory with applications to the study of interval computation ⋮ Resource restricted computability theoretic learning: Illustrative topics and problems ⋮ Two algorithms in search of a type-system ⋮ Speed-up theorems in type-2 computations using oracle Turing machines ⋮ Elementary explicit types and polynomial time operations ⋮ Axiomatizing Resource Bounds for Measure ⋮ Feasible functionals and intersection of ramified types ⋮ Representations and evaluation strategies for feasibly approximable functions ⋮ Polynomial Running Times for Polynomial-Time Oracle Machines ⋮ Characterizing polynomial time complexity of stream programs using interpretations ⋮ Quantitative coding and complexity theory of compact metric spaces

This page was built for publication: A new Characterization of Type-2 Feasibility