RAIRO-Theor. Inf. Appl.
Volume 44, Number 3, July-September 2010
|Page(s)||379 - 418|
|Published online||05 October 2010|
Function operators spanning the arithmetical and the polynomial hierarchy
Institut für Mathematik und Informatik.
17487 Greifswald, Germany; firstname.lastname@example.org
Accepted: 20 August 2010
A modified version of the classical µ-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory. The close relationships between nesting levels of operators and the stratification of the hierarchy also hold for suitable restrictions of the operators with respect to the polynomial hierarchy if one starts with the polynomial-time computable functions. It follows that questions around P vs. NP and NP vs. coNP can equivalently be expressed by closure properties of function classes under these operators. The polytime version of the first value operator can be used to establish hierarchies between certain consecutive levels within the polynomial hierarchy of functions, which are related to generalizations of the Boolean hierarchies over the classes .
Mathematics Subject Classification: 68Q15 / 03D15 / 03D55
Key words: Arithmetical hierarchy / polynomial hierarchy / Boolean hierarchy / P versus NP / NP versus coNP / first value operator / minimalization / inversion of functions
© EDP Sciences, 2010
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.