@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",
}