On the search for the definition of the space complexity for the calculation of polynomials using Valiant’s method. (À la recherche de la définition de la complexité d’espace pour le calcul des polynômes à la manière de Valiant.) (French) Zbl 1160.03020

Boolean and arithmetic circuits have been used extensively in current literature to analyze the complexity of map calculations. Valiant circuits are arithmetic circuits (inner nodes correspond to either addition or multiplication of two arguments provided by previous nodes) enlarged with nodes able to apply summation operators indexed by Boolean words. The input of the circuits are either of integer or Boolean type.
In this paper, several classes of maps are defined: VPdl, VPdb,VPmd and VPt, consisting, respectively, of maps calculated by sequences of arithmetic circuits of polynomial sizes, of polynomial sizes and polynomial circuit semidegrees, of polynomial sizes and polynomial circuit degrees, and of logarithmic heights. If \((u,v,x)\mapsto f(u,v,x)\) is a map in a class VP, where \(u\) and \(v\) are finite lists of Boolean variables, then let \(\sigma(f):(u,v,x)\mapsto \sum_vf(u,v,x)\). For any class VP, the class VNP consists of maps \(\sigma(f)\) with \(f\) in VP; and the class VSP is defined similarly as VP but considering Valiant circuits. The author claims that one main goal in considering such complexity classes lies in the construction of calculation models, in order to analyze the plausibility of those calculations, rather than in the construction of realistic models.
Several relations among these classes are examined (e.g. VNPt = VNPmd entails the #P-completeness of the calculation of the permanent) and the implausibility of some other are discussed (e.g. any of the relations \(\text{VNPmd}=\text{VPmd}\), \(\text{VNPdl}=\text{VPdl}\) or \(\text{VNPmd}\subset\text{VPdl}\) would imply \(\text{P}=\#\)P).
Let \(P_n\) be the map that, given two Boolean strings, produces the binomial coefficient of the integers whose base-2 representation are the input strings, and let \(F_n\) be the map defined similarly considering the factorial integer map. It is proved that \(P_n\) is in VSPdl, hence \(F_n\) is also in this class. Then, one may expect that VSPdl will differ from VPdl, because an efficient calculation of the factorial may solve efficiently the Integer Factorization Problem. It is also shown that if VNPmd = VPmd and P = PSPACE then \(F_n\) will fall into VPdl.
The above defined circuit classes are relativized to the arithmetic modulo a prime number, and some relations on the resulting classes are given. It is seen that P coincides with VPdl (modulo 2), while PSPACE coincides with VSPdl (modulo 2).
Then the author lists some sufficient conditions in order to have VSPdl = VPdl. However, the conditions indicate that it will not be possible to suppress summation operators in Valiant circuits in order to build equivalent circuits using just arithmetical nodes.
There are many unconventional notations the reader should be aware of. For instance, exponentiation, \(+^+\), is denoted via \(\land\), \(+\land+\). This is confusing in a first reading of the paper. Some intended exponentiations, \(2^j\), are displayed as products, \(2j\). And several intended subindexes appear as seemingly product factors .


03D15 Complexity of computation (including implicit computational complexity)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI


[1] Accessible telephone directories 59 pp 92– (1994)
[2] On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity 4393 (2007)
[3] Completeness and reduction in algebraic complexity theory (2000) · Zbl 0948.68082
[4] DOI: 10.1007/BF01200057 · Zbl 0774.68040
[5] DOI: 10.1137/0212043 · Zbl 0524.68028
[6] L’Enseignement Mathématique 30 pp 365– (1982)
[7] Soviet Physics – Doklady 7 pp 595– (1963)
[8] Les petits cailloux (1995)
[9] Characterizing Valiant’s algebraic complexity classes 4162 pp 267– (2006)
[10] DOI: 10.1145/321958.321973 · Zbl 0335.68022
[11] VPSPACE and a transfer theorem over the Reals 4393 (2007) · Zbl 1146.68379
[12] Computational Complexity 13 pp 131– (2004) · Zbl 1087.68566
[13] Proceedings of the 11th ACM STOC pp 249– (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.