A simple observation regarding iterations of finite-valued polynomial-time functions

• Autorzy: Mycka J.
• Języki publikacji: EN
• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2009
• Tom: Vol. 44
• Strony: 19--29
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Mycka J.

• Institute of Mathematics, University of Maria Curie-Sklodowska, Lublin, Poland,

Bibliografia

• [1] J. L. Balcázar, J. D´ıaz, and J. Gabarró, Structural Complexity I, Springer-Verlag, Second Edition, 1995.
• [2] S. Bellantoni, S. Cook, A new recursion-theoretic characterization of the polytime functions, Computational Complexity, 2, 2 (1992), pp. 97–110.
• [3] M.D. Gladstone, A reduction of a recursive scheme, J. Symb. Logic, 32 (1967), pp.505–508.
• [4] M.D. Gladstone, Simplification of the recursion scheme, J. Symb. Logic, 36 (1971), pp. 653–665.
• [5] J. Mycka, J. F. Costa, The P 6 not equal to NP conjecture in the context of real and complex analysis, Journal of Complexity, 22 (2006), pp. 287–303.
• [6] P. Odifreddi, Classical Recursion Theory, Elsevier, Vol. I, 1992, Vol. II, 1999.
• [7] C. Papadimitriou, Computational Complexity, Addison-Wesley 1994.
• [8] R.M. Robinson, Primitive recursive functions, Bull. Am. Math. Soc., 53 (1947), pp.925–942.
• [9] S.M. Tataram, Ackermann-Péter’s function has primitive recursive graph and range,Found. Control Engrg., 9, 4 (1984), pp. 177–180.