A new Characterization of Type-2 Feasibility
From MaRDI portal
Publication:4875448
DOI10.1137/S0097539794263452zbMATH Open0843.68028MaRDI QIDQ4875448FDOQ4875448
Authors: Bruce M. Kapron, Stephen Cook 
Publication date: 5 June 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Higher-type and set recursion theory (03D65)
Cited In (36)
- Feasible Iteration of Feasible Learning Functionals
- Speed-up theorems in type-2 computations using oracle Turing machines
- Exact real computation of solution operators for linear analytic systems of partial differential equations
- Semantics, specification logic, and Hoare logic of exact real computation
- Axiomatizing resource bounds for measure
- Parametrised second-order complexity theory with applications to the study of interval computation
- Computable analysis and notions of continuity in \textsc{Coq}
- Time polynomial in input or output
- Characterizing polynomial time complexity of stream programs using interpretations
- Game semantics approach to higher-order complexity
- Representations and evaluation strategies for feasibly approximable functions
- The basic feasible functionals in computable analysis
- Elementary explicit types and polynomial time operations
- A tier-based typed programming language characterizing feasible functionals
- A foundational delineation of poly-time
- Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
- Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
- Resource restricted computability theoretic learning: Illustrative topics and problems
- Two algorithms in search of a type-system
- Polynomial Running Times for Polynomial-Time Oracle Machines
- Type 2 polynomial hierarchies
- A tight relationship between generic oracles and type-2 complexity theory
- Title not available (Why is that?)
- Safe Weak Minimization Revisited
- On basic feasible functionals and the interpretation method
- A proof-theoretic characterization of the basic feasible functionals
- Quantitative continuity and Computable Analysis in Coq
- Some applications of logic to feasibility in higher types
- Feasible functionals and intersection of ramified types
- Complexity for type-2 relations
- A Relationship between Equilogical Spaces and Type Two Effectivity
- Theories with self-application and computational complexity.
- On the versatility of open logical relations. Continuity, automatic differentiation, and a containment theorem
- Title not available (Why is that?)
- Quantitative coding and complexity theory of compact metric spaces
- Feasible computability and resource bounded topology
This page was built for publication: A new Characterization of Type-2 Feasibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4875448)
