Bases for AC⁰ and Other Complexity Classes

• Autorzy: Mazzanti, S.
• Języki publikacji: EN

Abstrakty

EN

Function complexity classes are defined as the substitution closure of finite function sets by improving a method of elimination of concatenation recursion from function algebras. Consequently, the set of AC⁰ functions and other canonical complexity classes are defined as the substitution closure of a finite function set.

Słowa kluczowe

EN

concatenation recursion on notation; substitution basis

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 4
• Strony: 433--460
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Mazzanti, S.

• Dipartimento di Culture del Progetto Università Iuav di Venezia Fondamenta delle Terese 2206, 30123 Venezia, Italy,

Bibliografia

• [1] E. Allender, M. Loui and K. Regan, Reducibility and Completeness, in Algorithms and Theory of Computation Handbook, Second Edition, Volume 1: General Concepts and Techniques, ed. M. Atallah and M. Blanton, Chapman and Hall/CRC Applied Algorithms and Data Structures Series, CRC Press, 2009.
• [2] D.A.M. Barrington, N. Immerman, and H. Straubing. On Uniformity within NC1, J. Comput. System Sci. 41:3 (1990) 274–306.
• [3] P. Clote and G. Takeuti, First order bounded arithmetic and small Boolean circuit complexity classes, in Feasible Mathematics II, Birkhäuser Boston, 1995.
• [4] P. Clote, Sequential, machine-independent characterizations of the parallel complexity classes ALOGT IME,ACk,NCk and NC, in Feasible Mathematics, Birkhäuser, 1990.
• [5] P. Clote, Computation models and function algebras, in Handbook of Computability Theory, ed. E.R. Griffor, Elsevier Science B.V. (1999) 589-681.
• [6] S. Cook and P. Nguyen, Logical Foundations of Proof Complexity, Cambridge University Press, 2010.
• [7] W.M. Hesse, E. Allender, and D.A.M. Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, J. Comput. System Sci. 62:4 (2002) 695-716.
• [8] H. Ishihara, Function algebraic characterizations of the polytime functions, Comput. Complexity 8 (1999) 346–356.
• [9] J. P. Jones and Y. V. Matiyasevich, Basis for the polynomial time computable functions, in Proc. First Conf. Canadian Number Theory Assoc., Banff, Alberta, 1988, ed. R. A. Mollin, Walter de Gruyter, Berlin, (1990) 255-270.
• [10] S. S. Marcenkov, Elimination of recursion schemas in the Grzegorczyk E2 class, Math. Notes (1969) 5, 336–340.
• [11] S. Mazzanti, Plain bases for classes of primitive recursive functions, Math. Log. Quart. 48 (2002) 93-104.
• [12] S. Mazzanti, CRN elimination and substitution bases for complexity classes, Fund. Inform. 120:1 (2012) 29-58.
• [13] A. A. Muchnik, On two approaches to the classification of recursive functions, in Problems of Mathematical Logic, Complexity of Algorithms and Classes of Computable Functions, eds. V. A. Kozminiadi and A. A. Muchnik, Mir, Moscow, (1970) 123-138 (in Russian).
• [14] P. Nguyen, Bounded Reverse Mathematics, PhD Thesis, University of Toronto, 2008.
• [15] S. A. Volkov, An example of a simple quasi-universal function in the class E2 of the Grzegorczyk hierarchy, Discrete Mathematics and Applications 16, 5 (2006) 513-526.
• [16] S. A. Volkov, Generating Some Classes of Recursive Functions by Superpositions of Simple Arithmetic Functions, Dokl. Akad. Nauk 415, 4 (2007) 439-440. English translation Dokl. Math. 76, 1 (2007) 566-567.
• [17] S. A. Volkov, http://volkov-articles.narod.ru/ffom_manyfloors.pdf .

Identyfikatory

DOI

10.3233/FI-2015-1165