CIRCUITS, MATRICES, AND NONASSOCIATIVE COMPUTATION
CIRCUITS, MATRICES, AND NONASSOCIATIVE COMPUTATION
复制标题
DOI：
10.1006/jcss.1995.1035
复制
发表时间：
1995-06-01
影响因子：
1.1
通讯作者：
MCKENZIE, P
中科院分区：
文献类型：
--
作者：
BEAUDRY, M;MCKENZIE, P
我们考虑了非结合代数结构上各种计算问题的复杂性。具体来说，我们看看问题的评估电路，公式和单词，在两个非关联结构本身和矩阵与这些结构中的元素。扩展过去的工作，我们表明，这些问题可以表征各种各样的复杂性类，包括NP。作为示例，单词（即，迭代乘法）问题，涉及结构（S; +，）上的O（log（k）n）个矩阵序列，其中（S; +）是么半群或非周期么半群，分别对NC k +1和AC（k）是完备的，而一个涉及大小为O（log（k）n）的矩阵的字问题变体对SCk是完备的. (C)北京：科学出版社. Inc.
We consider the complexity of various computational problems over nonassociative algebraic structures. Specifically, we look at the problem of evaluating circuits, formulas, and words, over both nonassociative structures themselves and over matrices with elements in these structures. Extending past work, we show that such problems can characterize a wide variety of complexity classes up to and including NP. As an example, the word (i.e., iterated multiplication) problems involving a sequence of O(log(k) n) matrices over a structure ( S; +,) in which (S; +) is a monoid or an aperiodic monoid are complete for NCk+1 and for AC(k), respectively, and a word problem variant involving matrices of size O(log(k) n) is complete for SCk. (C) 1995 Academic Press. Inc.