TY - JOUR
T1 - On the computational complexity of Longley's H functional
AU - Royer, James S.
N1 - Funding Information:
The author wishes to thank John Longley, Sue Older, and the anonymous referees for numerous comments that helped to greatly improve the paper. Thanks, as always, to Elaine Weinman for her careful comments on the text. This work was supported in part by NSF grants CCR-9522987 and CCR-0098198.
PY - 2004/6/6
Y1 - 2004/6/6
N2 - Longley discovered a functional H that, when added to PCF, yields a language that computes exactly SR, the sequentially realizable functionals of van Oosten. We show that if P≠NP, then the computational complexity of H (and of similar SR-functionals) is inherently infeasible.
AB - Longley discovered a functional H that, when added to PCF, yields a language that computes exactly SR, the sequentially realizable functionals of van Oosten. We show that if P≠NP, then the computational complexity of H (and of similar SR-functionals) is inherently infeasible.
KW - Higher-type computational complexity
KW - NP-hardness
KW - Realizability
KW - Sequential computability
UR - http://www.scopus.com/inward/record.url?scp=2442444908&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2442444908&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2003.10.024
DO - 10.1016/j.tcs.2003.10.024
M3 - Conference Article
AN - SCOPUS:2442444908
SN - 0304-3975
VL - 318
SP - 225
EP - 241
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -