Por Isabel Oitavem (FCT - Universidade Nova de Lisboa).

We give recursion-theoretic characterizations of all levels of the polynomial hierarchy of time and of the hierarchy itself. We characterize both, the $\Box^P_n$ and the $\Sigma^P_n$ 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.

Zoom Meeting | ID da reunião: 890 8479 3299 - senha de acesso: 409604