On the computational complexity of Longley's H functional

James S. Royer

Research output: Contribution to journalConference Articlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)225-241
Number of pages17
JournalTheoretical Computer Science
Issue number1-2
StatePublished - Jun 6 2004


  • Higher-type computational complexity
  • NP-hardness
  • Realizability
  • Sequential computability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the computational complexity of Longley's H functional'. Together they form a unique fingerprint.

Cite this