Verifying the determinant in parallel
Verifying the determinant in parallel
复制标题
并行验证行列式
DOI：
--
复制
发表时间：
1994
影响因子：
1.4
通讯作者：
Sovanna Tan
中科院分区：
文献类型：
--
作者：
M. Santha;Sovanna Tan
摘要。本文研究了布尔算术电路和布尔电路模型中计算等价于行列式的验证问题的复杂性。我们观察到，对于一些问题，存在一个简单的（NC1）验证算法。为了描述较难的问题，我们定义了在两种不同的约简下可简化为行列式验证的问题类别，并建立了这些类别中完整问题的列表。特别地，我们证明了在AC0约简下计算秩与验证行列式是等价的。我们证明在布尔情况下，除非L = NL，否则在NC1中没有一个完全问题可以被识别。另一方面，我们证明了对于函数，即使它们很难验证，也存在一个NC1检查器，并且它们可以扩展为易于验证的函数。
Abstract. In this paper, we investigate the complexity of verifying problems whose computation is equivalent to the determinant, both in the Boolean arithmetic circuit and in the Boolean circuit model. We observe that for a few problems, there exists an easy (NC1) verification algorithm. To characterize the harder ones, we define the class of problems that are reducible to the verification of the determinant, under two different reductions, and establish a list of complete problems in these classes. In particular, we prove that computing the rank is equivalent under AC0 reductions to verifying the determinant. We show in the Boolean case that none of the complete problems can be recognized in NC1 unless L = NL. On the other hand, we show that for functions, there exists an NC1 checker even if they are hard to verify, and that they can be extended into functions whose verification is easy.