Relationships among PL, #L, and the determinant
Relationships among PL, #L, and the determinant
复制标题
PL之间的关系，
DOI：
10.1109/sct.1994.315797
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Mitsunori Ogihara
中科院分区：
文献类型：
--
作者：
Eric Allender;Mitsunori Ogihara
Toda (1991)、Vinay (1991)、Damm (1991) 和 Valiant (1992) 的结果表明，行列式的复杂性由计算非确定性对数空间有界机器的接受计算数量的复杂性来表征。 （此类函数称为 L。）通过使用该特征并建立一些基本闭包属性，我们给出了 Jung (1985) 定理的非常简单的证明，表明概率对数空间有界 (PL) 机器如果被限制在多项式时间内运行，则不会失去任何计算能力。我们还使用各种可简化性概念，比较和对比可简化为 PL、#L 和行列式的函数类别，提出了新的结果。<<ETX>>
Results by Toda (1991), Vinay (1991), Damm (1991), and Valiant (1992) have shown that the complexity of the determinant is characterized by the complexity of counting the number of accepting computations of a nondeterministic logspace-bounded machine. (This class of functions is known as L.) By using that characterization and by establishing a few elementary closure properties, we give a very simple proof of a theorem of Jung (1985), showing that probabilistic logspace-bounded (PL) machines lose none of their computational power if they are restricted to run in polynomial time. We also present new results comparing and contrasting the classes of functions reducible to PL, #L, and the determinant, using various notions of reducibility.<<ETX>>