Type-two polynomial-time and restricted lookahead

DOI10.1016/j.tcs.2019.07.003zbMath1471.03070arXiv1801.07485OpenAlexW2784921327WikidataQ127589634 ScholiaQ127589634MaRDI QIDQ1989320

Florian Steinberg, Bruce M. Kapron

Publication date: 21 April 2020

Published in: Theoretical Computer Science, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.07485

zbMATH Keywords

oracle Turing machineoracle Turing machineshigher-order computabilitycomputability in higher typestype-two polynomial timeapplied lambda-calculusfeasibility of functionals

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Higher-type and set recursion theory (03D65)

Related Items (5)

Unnamed Item ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Quantitative continuity and Computable Analysis in Coq ⋮ Unnamed Item ⋮ Quantitative coding and complexity theory of compact metric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Functional interpretations of feasibly constructive arithmetic
• A proof-theoretic characterization of the basic feasible functionals
• Complexity for type-2 relations
• Relativized alternation and space-bounded computation
• A new recursion-theoretic characterization of the polytime functions
• Polynomial and abstract subrecursive classes
• The relative complexity of NP search problems
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• On the computational complexity of Longley's \(H\) functional
• Game semantics approach to higher-order complexity
• On characterizations of the basic feasible functionals, Part I
• Small Complexity Classes for Computable Analysis
• Complexity Theory for Operators in Analysis
• Spaces allowing Type‐2 Complexity Theory revisited
• A new Characterization of Type-2 Feasibility
• Type-Based Complexity Analysis for Fork Processes
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Some applications of logic to feasibility in higher types
• Adventures in time and space
• The complexity of theorem-proving procedures
• Resource-bounded continuity and sequentiality for type-two functionals

This page was built for publication: Type-two polynomial-time and restricted lookahead