Function operators spanning the arithmetical and the polynomial hierarchy

Armin Hemmerling

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 3, page 379-418
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Hemmerling, Armin. "Function operators spanning the arithmetical and the polynomial hierarchy." RAIRO - Theoretical Informatics and Applications 44.3 (2010): 379-418. <http://eudml.org/doc/250758>.

@article{Hemmerling2010,
abstract = { 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 $\mbox\{$\Sigma^p\_\{k\}$\}$. },
author = {Hemmerling, Armin},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Arithmetical hierarchy; polynomial hierarchy; Boolean hierarchy; P versus NP; NP versus coNP; first value operator; minimalization; inversion of functions; arithmetical hierarchy; Boolean hierarchy; P versus NP; first value operator},
language = {eng},
month = {10},
number = {3},
pages = {379-418},
publisher = {EDP Sciences},
title = {Function operators spanning the arithmetical and the polynomial hierarchy},
url = {http://eudml.org/doc/250758},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Hemmerling, Armin
TI - Function operators spanning the arithmetical and the polynomial hierarchy
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/10//
PB - EDP Sciences
VL - 44
IS - 3
SP - 379
EP - 418
AB - 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 $\mbox{$\Sigma^p_{k}$}$.
LA - eng
KW - Arithmetical hierarchy; polynomial hierarchy; Boolean hierarchy; P versus NP; NP versus coNP; first value operator; minimalization; inversion of functions; arithmetical hierarchy; Boolean hierarchy; P versus NP; first value operator
UR - http://eudml.org/doc/250758
ER -

References

top
  1. S. Buss and L. Hay, On truth-table reducibility to SAT. Inf. Comput.91 (1991) 86–102.  Zbl0800.68443
  2. J.L. Balcazar, J. Diaz and J. Gabarro, Structural complexity I and II. Springer-Verlag, Berlin (1990).  Zbl0746.68032
  3. S.J. Bellantoni and K.-H. Niggl, Ranking primitive recursions: the low Grzegorczyk classes revised. SIAM Journal on Computing29 (1999) 401–415.  Zbl0939.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 Computing17 (1988) 1232–1252.  Zbl0676.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 Computing18 (1989) 95–111.  Zbl0676.68012
  6. S.B. Cooper, Computability theory. Chapman & Hall/CRC, Boca Raton (2004).  
  7. D.-Z. Du and K.-I. Ko, Theory of computational complexity. Wiley-Interscience, New York (2000).  
  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.  
  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.).  Zbl0216.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).  Zbl0411.68039
  11. F. Hausdorff, Grundzüge der Mengenlehre. W. de Gruyter & Co., Berlin and Leipzig (1914); Reprint: Chelsea P.C., New York (1949).  
  12. A. Hemmerling, The Hausdorff-Ershov hierarchy in Euclidean spaces. Arch. Math. Logic45 (2006) 323–350.  Zbl1095.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 Science120 (2005) 59–72.  
  14. J. Krajicek, Bounded arithmetic, propositional logic, and complexity theory. Cambridge Univ. Press (1995).  Zbl0835.03025
  15. M.W. Krentel, The complexity of optimization problems. J. Comput. Syst. Sci.36 (1988) 490–509.  Zbl0652.68040
  16. A.I. Malcev, Algorithmen und rekursive Funktionen. Akademie-Verlag, Berlin (1974).  
  17. P. Odifreddi, Classical recursion theory. North-Holland P.C., Amsterdam (1989).  Zbl0661.03029
  18. C.H. Papadimitriou, Computational complexity. Addison Wesley P.C., Reading (1994).  Zbl0833.68049
  19. C. Parsons, Hierarchies of primitive recursive functions. Zeitschr. f. Math. Logik u. Grundl. d. Math. 14 (1968) 357–376.  Zbl0172.29703
  20. J. Robinson, General recursive functions. Proc. Am. Math. Soc.72 (1950) 703–718.  Zbl0041.15101
  21. H. Rogers Jr, Theory of recursive functions and effective computability. McGraw-Hill, New York (1967).  
  22. H.E. Rose, Subrecursion: functions and hierarchies. Clarendon Press, Oxford (1984).  Zbl0539.03018
  23. J. Rothe, Complexity theory and cryptology. Springer-Verlag, Berlin (2005).  Zbl1082.94002
  24. H. Schwichtenberg, Rekursionszahlen und Grzegorczyk-Hierarchie. Arch. Math. Logic12 (1969) 85–97.  
  25. A.L. Selman, A survey of one-way functions in complexity theory. Math. Syst. Theory25 (1992) 203–221.  Zbl0749.68037
  26. A. Selman, A taxonomy of complexity classes of functions. J. Comput. Syst. Sci.48 (1994) 357–381.  Zbl0806.68049
  27. J.R. Shoenfield, On degrees of unsolvability. Ann. Math.69 (1959) 644–653.  Zbl0119.25105
  28. R.I. Soare, Recursively enumerable sets and degrees. Springer-Verlag, Berlin (1987).  Zbl0667.03030
  29. R.I. Soare, Computability and recursion. Bulletin of symbolic Logic2 (1996) 284–321.  Zbl0861.03031
  30. R.I. Soare, Computability theory and applications. Springer-Verlag, Berlin, forthcoming.  Zbl06236171
  31. K.W. Wagner, Bounded query classes. SIAM Journal on Computing19 (1990) 833–846.  Zbl0711.68047
  32. G. Wechsung, Vorlesungen zur Komplexitätstheorie. B.G. Teubner, Stuttgart (2000).  
  33. K. Weihrauch, Computability. Springer-Verlag, Berlin (1987).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.