The polynomial hierarchy of functions and its levels

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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
Volume900
DOIs
Publication statusPublished - 8 Jan 2022

Keywords

  • Implicit complexity
  • Polynomial hierarchy
  • Tree-recursion

Fingerprint

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

Cite this