Characterizing Valiant's algebraic complexity classes
Characterizing Valiant's algebraic complexity classes
复制标题
DOI：
10.1016/j.jco.2006.09.006
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
Guillaume Malod;Natacha Portier
中科院分区：
文献类型：
--
作者：
Guillaume Malod;Natacha Portier
Valiant在20年前引入了代数复杂性理论来研究多项式族的复杂性。使用的基本计算模型是算术电路，这使得这些类非常容易定义和开放组合技术。在本文中，我们在一个统一的主题下收集已知的结果和新技术，即对电路门施加的限制，建立从公式到电路的层次结构。因此，我们得到了已知结果的更简单的证明，如类VNP和VNPeor类VQP的行列式的完备性，以及新的结果，如类VQP和VP的表征（我们也可以应用于布尔类LOGCFL）或对b<s:1> rgisser的书中的猜想的完整答案[代数复杂性理论的完备性和约简，数学中的算法和计算，卷7，施普林格，柏林，2000]。我们还证明了对于多项式深度和无界大小的电路，这些模型都具有相同的表达能力，并且可以用来表征VNP的统一版本。
Valiant introduced 20 years ago an algebraic complexity theory to study the complexity of polynomial families. The basic computation model used is the arithmetic circuit, which makes these classes very easy to define and open to combinatorial techniques. In this paper we gather known results and new techniques under a unifying theme, namely the restrictions imposed upon the gates of the circuit, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and VNPeor the completeness of the Determinant for VQP, and new results such as a characterization of the classes VQP and VP (which we can also apply to the Boolean class LOGCFL) or a full answer to a conjecture in Bürgisser's book [Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer, Berlin, 2000]. We also show that for circuits of polynomial depth and unbounded size these models all have the same expressive power and can be used to characterize a uniform version of VNP.