In the first half of the 1990s, Clote and Takeuti characterized several function complexity classes by means of the concatenation recursion on notation operators. In this paper, we borrow from computability theory well-known techniques based on pairing functions to show that AC0,TC0, NC1, and NC functions can be characterized by means of concatenation iteration on notation. Indeed, a function class satisfying simple constraints and defined by using concatenation recursion on notation is inductively characterized by means of concatenation iteration on notation. Furthermore, AC0,TC0, NC1, and NC unary functions are inductively characterized using addition, composition, and concatenation iteration on notation.
Iteration on notation and unary functions
MAZZANTI, STEFANO
2013-01-01
Abstract
In the first half of the 1990s, Clote and Takeuti characterized several function complexity classes by means of the concatenation recursion on notation operators. In this paper, we borrow from computability theory well-known techniques based on pairing functions to show that AC0,TC0, NC1, and NC functions can be characterized by means of concatenation iteration on notation. Indeed, a function class satisfying simple constraints and defined by using concatenation recursion on notation is inductively characterized by means of concatenation iteration on notation. Furthermore, AC0,TC0, NC1, and NC unary functions are inductively characterized using addition, composition, and concatenation iteration on notation.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
