Characterizing Valiant's algebraic complexity classes
| Autor: | Guillaume Malod, Natacha Portier |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Statistics and Probability
Class (set theory) Polynomial Control and Optimization Geometric complexity theory Computer science General Mathematics Determinant Computer Science::Computational Complexity Mathematical proof Polynomials Reduction (complexity) Circuits Completeness (order theory) Permanent Arithmetic circuit complexity LOGCFL Formulas Discrete mathematics Numerical Analysis Algebraic complexity Algebra and Number Theory Straight line programs Applied Mathematics Skew circuits Algebra Valiant's theory |
| Zdroj: | Journal of Complexity. 24:16-38 |
| ISSN: | 0885-064X |
| DOI: | 10.1016/j.jco.2006.09.006 |
| Popis: | 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 VNPe or 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect