Two function algebras defining functions in boolean circuits

详细信息    查看全文

• 作者：Guillaume Bonfante^a ; ¹ ; ^{bonfante@loria.fr" class="auth_mail" title="E-mail the corresponding author} ; Reinhard Kahle^b ; ² ; ^{kahle@mat.uc.pt" class="auth_mail" title="E-mail the corresponding author} ; Jean-Yves Marion^a ; ¹ ; ^{jean-yves.marion@loria.fr" class="auth_mail" title="E-mail the corresponding author} ; Isabel Oitavem^b ; ² ; ^{oitavem@fct.unl.pt" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Boolean circuits ; NCkNCk ; Parallel computation class ; Transducers
• 刊名：Information and Computation
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：248
• 期：Complete
• 页码：82-103
• 全文大小：657 K

文摘

We describe the functions computed by boolean circuits in ccdf6ed04405e" title="Click to view the MathML source">NC^k${\mathsf{NC}}^k$ by means of functions algebra for k≥1$k\ge 1$ in the spirit of implicit computational complexity. The whole hierarchy defines NC$\mathsf{NC}$. In other words, we give a recursion-theoretic characterization of the complexity classes ccdf6ed04405e" title="Click to view the MathML source">NC^k${\mathsf{NC}}^k$ for k≥1$k\ge 1$ without reference to a machine model, nor explicit bounds in the recursion schema. Actually, we give two equivalent descriptions of the classes ccdf6ed04405e" title="Click to view the MathML source">NC^k${\mathsf{NC}}^k$, k≥1$k\ge 1$. One is based on a tree structure à la Leivant, the other is based on words. This latter puts into light the role of computation of pointers in circuit complexity. We show that transducers are a key concept for pointer evaluation.