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.
- Higher-type computational complexity
- Sequential computability
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)