The polynomial hierarchy of functions and its levels

Isabel Oitavem

doi:10.1016/j.tcs.2021.11.016

The polynomial hierarchy of functions and its levels

Isabel Oitavem

Research output: Contribution to journal › Article › peer-review

3 Citations (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 □_n^P and the Σ_n^P 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 language	English
Pages (from-to)	25-34
Number of pages	10
Journal	Theoretical Computer Science
Volume	900
DOIs	https://doi.org/10.1016/j.tcs.2021.11.016
Publication status	Published - 8 Jan 2022

Keywords

Implicit complexity
Polynomial hierarchy
Tree-recursion

Access to Document

10.1016/j.tcs.2021.11.016

Cite this

@article{3e93d70c5638420185d8241a10513e14,

title = "The polynomial hierarchy of functions and its levels",

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.",

keywords = "Implicit complexity, Polynomial hierarchy, Tree-recursion",

author = "Isabel Oitavem",

note = "Funding Information: info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB\%2F00297\%2F2020/PT\# National funds through the FCT - Funda??o para a Ci{\^e}ncia e Tecnologia, I.P. Funding Information: info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB\%2F00297\%2F2020/PT National funds through the FCT - Funda{\c c}{\~a}o para a Ci{\^e}ncia e Tecnologia, I.P. Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = jan,

day = "8",

doi = "10.1016/j.tcs.2021.11.016",

language = "English",

volume = "900",

pages = "25--34",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - The polynomial hierarchy of functions and its levels

AU - Oitavem, Isabel

N1 - Funding Information: info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00297%2F2020/PT# National funds through the FCT - Funda??o para a Ciência e Tecnologia, I.P. Funding Information: info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00297%2F2020/PT National funds through the FCT - Fundação para a Ciência e Tecnologia, I.P. Publisher Copyright: © 2021 Elsevier B.V.

PY - 2022/1/8

Y1 - 2022/1/8

N2 - 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.

AB - 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.

KW - Implicit complexity

KW - Polynomial hierarchy

KW - Tree-recursion

UR - https://www.scopus.com/pages/publications/85120773353

U2 - 10.1016/j.tcs.2021.11.016

DO - 10.1016/j.tcs.2021.11.016

M3 - Article

AN - SCOPUS:85120773353

SN - 0304-3975

VL - 900

SP - 25

EP - 34

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

The polynomial hierarchy of functions and its levels

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this