On the computational complexity of Longley's H functional

James S. Royer

Research output: Contribution to journalConference article

3 Scopus citations

Abstract

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
Volume318
Issue number1-2
DOIs
StatePublished - Jun 6 2004

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this