The polynomial hierarchy of functions and its levels

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We give recursion-theoretic characterizations of all levels of the polynomial hierarchy of time and of the hierarchy itself. We characterize both, the □nP and the ΣnP levels. In this work, only composition and recursion schemes are used. We identify the recursion scheme which added to FPtime leads to the full polynomial hierarchy.

Original languageEnglish
Pages (from-to)25-34
Number of pages10
JournalTheoretical Computer Science
Publication statusPublished - 8 Jan 2022


  • Implicit complexity
  • Polynomial hierarchy
  • Tree-recursion


Dive into the research topics of 'The polynomial hierarchy of functions and its levels'. Together they form a unique fingerprint.

Cite this