Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹
复制标题
有界宽度多项式大小分支程序可以准确识别 NC 中的那些语言
DOI：
10.1016/0022-0000(89)90037-8
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
D. A. Barrington
中科院分区：
文献类型：
--
作者：
D. A. Barrington
我们表明，任何语言识别NC 1电路（扇入2，深度O（logn））可以识别的一种特定类型的宽度5多项式大小的分支程序。由于任何有界宽度多项式大小的分支程序都可以用NC 1电路来模拟，因此我们得出这样的程序所识别的语言类是完全非一致的NC 1。而且，在Ruzzo [Ru 81]和Cook [Co 85]的基础上，如果分支程序被限制为ATIME（log n）一致的，则它们识别的语言与ATIME（log n）-不一致NC 1电路识别的语言相同，即ATIME（log n）中的语言。我们还扩展了证明的方法，以调查的复杂性字的问题，为一个固定的置换群。
We show that any language recognized by an NC 1 circuit (fan-in 2, depth O (logn)) can be recognized by a particular type of width 5 polynomial-size branching program. As any bounded-width polynomial-size branching program can be simulated by an NC 1 circuit, we have that the class of languages recognized by such programs is exactly non-uniform NC 1. Fur-ther, following Ruzzo [Ru81] and Cook [Co85], if the branching programs are restricted to be ATIME (log n) uniform, they recognize the same languages as do ATIME (log n)-unfform NC 1 circuits, that is, those languages in ATIME (log n). We also extend the method of proof to investigate the complexity of the word problem for a fixed permutation group.