On the computational complexity of Longley's \(H\) functional

DOI10.1016/j.tcs.2003.10.024zbMath1077.68035OpenAlexW2108736782MaRDI QIDQ1827400

James S. Royer

Publication date: 6 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.024

zbMATH Keywords

NP-hardnessRealizabilityHigher-type computational complexitySequential computability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Type-two polynomial-time and restricted lookahead ⋮ A stable programming language ⋮ The sequentially realizable functionals

Cites Work

• Functional interpretations of feasibly constructive arithmetic
• Classical recursion theory. Vol. II
• The sequentially realizable functionals
• On characterizations of the basic feasible functionals, Part I
• When is a functional program not a functional program?
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item