Function operators spanning the arithmetical and the polynomial hierarchy
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 379-418.

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 Σ k p .

DOI : https://doi.org/10.1051/ita/2010020
Classification : 68Q15,  03D15,  03D55
Mots clés : arithmetical hierarchy, polynomial hierarchy, boolean hierarchy, P versus NP, NP versus conp, first value operator, minimalization, inversion of functions
@article{ITA_2010__44_3_379_0,
     author = {Hemmerling, Armin},
     title = {Function operators spanning the arithmetical and the polynomial hierarchy},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {379--418},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {3},
     year = {2010},
     doi = {10.1051/ita/2010020},
     zbl = {1213.68294},
     mrnumber = {2761525},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2010020/}
}
TY  - JOUR
AU  - Hemmerling, Armin
TI  - Function operators spanning the arithmetical and the polynomial hierarchy
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
DA  - 2010///
SP  - 379
EP  - 418
VL  - 44
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2010020/
UR  - https://zbmath.org/?q=an%3A1213.68294
UR  - https://www.ams.org/mathscinet-getitem?mr=2761525
UR  - https://doi.org/10.1051/ita/2010020
DO  - 10.1051/ita/2010020
LA  - en
ID  - ITA_2010__44_3_379_0
ER  - 
Hemmerling, Armin. Function operators spanning the arithmetical and the polynomial hierarchy. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 379-418. doi : 10.1051/ita/2010020. http://www.numdam.org/articles/10.1051/ita/2010020/

[1] S. Buss and L. Hay, On truth-table reducibility to SAT. Inf. Comput. 91 (1991) 86-102. | Zbl 0800.68443

[2] J.L. Balcazar, J. Diaz and J. Gabarro, Structural complexity I and II. Springer-Verlag, Berlin (1990). | Zbl 0826.68048

[3] S.J. Bellantoni and K.-H. Niggl, Ranking primitive recursions: the low Grzegorczyk classes revised. SIAM Journal on Computing 29 (1999) 401-415. | Zbl 0939.03042

[4] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sawelson, K. Wagner and G. Wechsung, The Boolean hierarchy I: structural properties. SIAM Journal on Computing 17 (1988) 1232-1252. | Zbl 0676.68011

[5] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sawelson, K. Wagner and G. Wechsung, The Boolean hierarchy II: applications. SIAM Journal on Computing 18 (1989) 95-111. | Zbl 0676.68012

[6] S.B. Cooper, Computability theory. Chapman & Hall/CRC, Boca Raton (2004). | Zbl 1041.03001

[7] D.-Z. Du and K.-I. Ko, Theory of computational complexity. Wiley-Interscience, New York (2000). | Zbl 1001.68050

[8] R.L. Epstein, R. Haas and R.L. Kramer, Hierarchies of sets and degrees below 0'. In: Logic Year (1979/80), Univ. of Connecticut, edited by M. Lerman, J.H. Schmerl, R.I. Soare. LN in Math 859. Springer Verlag, 32-48. | Zbl 0467.03046

[9] Y.L. Ershov, A hierarchy of sets. I; II; III. Algebra i Logica 7 (1968) no. 1, 47-74; no. 4, 15-47; 9 (1970), no. 1, 34-51 (English translation by Plenum P.C.). | Zbl 0216.00901

[10] M.R. Garey and D.S. Johnson, Computers and intractability - a guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979). | Zbl 0411.68039

[11] F. Hausdorff, Grundzüge der Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig (1914); Reprint: Chelsea P.C., New York (1949). | JFM 53.0169.01

[12] A. Hemmerling, The Hausdorff-Ershov hierarchy in Euclidean spaces. Arch. Math. Logic 45 (2006) 323-350. | Zbl 1095.03031

[13] A. Hemmerling, Hierarchies of function classes defined by the first-value operator. RAIRO - Theor. Inf. Appl. 42 (2008) 253-270. Extended abstract in: Proc. of CCA'2004. Electronic Notes in Theoretical Computer Science 120 (2005) 59-72. | Numdam | Zbl 1146.03032

[14] J. Krajicek, Bounded arithmetic, propositional logic, and complexity theory. Cambridge Univ. Press (1995). | Zbl 0835.03025

[15] M.W. Krentel, The complexity of optimization problems. J. Comput. Syst. Sci. 36 (1988) 490-509. | Zbl 0652.68040

[16] A.I. Malcev, Algorithmen und rekursive Funktionen. Akademie-Verlag, Berlin (1974). | Zbl 0285.02034

[17] P. Odifreddi, Classical recursion theory. North-Holland P.C., Amsterdam (1989). | Zbl 0661.03029

[18] C.H. Papadimitriou, Computational complexity. Addison Wesley P.C., Reading (1994). | Zbl 0833.68049

[19] C. Parsons, Hierarchies of primitive recursive functions. Zeitschr. f. Math. Logik u. Grundl. d. Math. 14 (1968) 357-376. | Zbl 0172.29703

[20] J. Robinson, General recursive functions. Proc. Am. Math. Soc. 72 (1950) 703-718. | Zbl 0041.15101

[21] H. Rogers Jr, Theory of recursive functions and effective computability. McGraw-Hill, New York (1967). | Zbl 0183.01401

[22] H.E. Rose, Subrecursion: functions and hierarchies. Clarendon Press, Oxford (1984). | Zbl 0539.03018

[23] J. Rothe, Complexity theory and cryptology. Springer-Verlag, Berlin (2005). | Zbl 1082.94002

[24] H. Schwichtenberg, Rekursionszahlen und Grzegorczyk-Hierarchie. Arch. Math. Logic 12 (1969) 85-97. | Zbl 0213.01801

[25] A.L. Selman, A survey of one-way functions in complexity theory. Math. Syst. Theory 25 (1992) 203-221. | Zbl 0749.68037

[26] A. Selman, A taxonomy of complexity classes of functions. J. Comput. Syst. Sci. 48 (1994) 357-381. | Zbl 0806.68049

[27] J.R. Shoenfield, On degrees of unsolvability. Ann. Math. 69 (1959) 644-653. | Zbl 0119.25105

[28] R.I. Soare, Recursively enumerable sets and degrees. Springer-Verlag, Berlin (1987). | Zbl 0667.03030

[29] R.I. Soare, Computability and recursion. Bulletin of symbolic Logic 2 (1996) 284-321. | Zbl 0861.03031

[30] R.I. Soare, Computability theory and applications. Springer-Verlag, Berlin, forthcoming.

[31] K.W. Wagner, Bounded query classes. SIAM Journal on Computing 19 (1990) 833-846. | Zbl 0711.68047

[32] G. Wechsung, Vorlesungen zur Komplexitätstheorie. B.G. Teubner, Stuttgart (2000). | Zbl 0965.68024

[33] K. Weihrauch, Computability. Springer-Verlag, Berlin (1987). | Zbl 0611.03002

Cité par Sources :