{'fraction_non_alphanumeric': 0.05564012268544814, 'fraction_numerical': 0.011973190957628081, 'mean_word_length': 3.616740088105727, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 39, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
P versus NP and geometry

I describe three geometric approaches to resolving variants of P v. NP, present several results that illustrate the role of group actions in complexity theory, and make a first step towards completely geometric definitions of complexity classes.


Introduction
The purpose of this article is to explain some of the beautiful problems in geometry that arise in the study of P versus NP and to motivate geometers to work on them. The article is divided into three parts: (i) holographic algorithms, where surprising reductions in complexity are related to the geometry of complex Hermitian symmetric spaces, in particular the variety of pure spinors, (ii) comparing the complexity of computing the permanent and determinant polynomials, where local differential geometry, geometric invariant theory and representation theory all play a role, and (iii) first steps towards describing geometric (i.e., coordinate free) definitions of algebraic complexity classes. While these parts are formally unrelated, there are common themes arising in each case, most importantly, (possibly hidden) group actions.
Roughly speaking, a problem in complexity theory is a class of expressions to be evaluated (e.g. count the number of four colorings of a planar graph). An instance of a problem is a particular member of the class (e.g. count the number of four colorings of the complete graph with four vertices). P is the class of problems that admit an algorithm that solves any instance of it in a number of steps that depends polynomialy on the size of the input data. One says that such problems "admit a polynomial time solution". NP is the class of problems where a proposed solution to an instance can be positively checked in polynomial time. The famous Cook's hypothesis is P = NP.
I will be concerned with two types of evaluations in this article, here is the first: For each n, let V n be a complex vector space and assume dim(V n ) grows exponentially with n. It is known that the pairing of the vector space with its dual requires on the order of dim(V n ) arithmetic operations to perform. However if V n has additional structure and α, v are in "special position" with respect to this structure, the pairing can be evaluated faster. A trivial example would be if V n were equipped with a basis and v was restricted to be a linear combination of only the first few basis vectors. I will be concerned with more subtle examples such as the following: let V n = Λ k C n , then inside V n are the decomposable vectors (the cone over the Grassmannian G(k, C n )). If α, v are decomposable, equation (3.1.1) shows that the pairing α, v can be evaluated in polynomial time in n. From a geometric perspective, this is one of the key ingredients to L. Valiant's holographic algorithms discussed in §2 and §4. For n large, the codimension of the Grassmannian supported by NSF grant DMS-0805782. 1 is huge, so it would seem highly unlikely that any interesting problem could have α, v so special. However small Grassmannians are of small codimension. This leads to the second key ingredient to holographic algorithms. On the geometric side, if [v 1 ] ∈ G(k 1 , W 1 ) and [v 2 ] ∈ G(k 2 , W 2 ), then [v 1 ⊗ v 2 ] ∈ G(k 1 k 2 , W 1 ⊗ W 2 ). Thus if our vectors can be thought of as being built out of vectors in smaller spaces, there is a much better chance of the vectors lying in the Grassmannian. Due to the nature of problems in complexity theory, this is exactly what occurs. The third key ingredient is that there is some flexibility in how the small vector spaces are equipped with the additional structure, and I show (Theorem 4.2.2) that even for NP-complete problems there is sufficient flexibility to allow everything to work up to this point. The difficulty occurs when one tries to glue together the small vector spaces compatibly for both V n and V * n , although even here, the "only" problem that can occur is one of signs, see §4. 3.
The second type of evaluation I will be concerned with is that of sequences of (homogeneous) polynomials, p n ∈ S d(n) C v(n) , where the degree d(n) and the number of variables v(n) are required to grow at most polynomialy with n. A generic such sequence is known to require an exponential (in n) number of arithmetic operations to evaluate and we are interested in characterizing the sequences where the evaluation can be done quickly. Again there are sequences such as p n = x d(n) 1 +· · ·+x d(n) v(n) where it is trivial to see that there is a polynomial time evaluation, but there are other, more subtle examples, such as det n ∈ S n C n 2 where the fast evaluation occurs thanks to a group action (Gaussian elimination, see §7.1).
From a geometer's perspective, it is more interesting to look at the zero sets of the polynomials, to get sequences of hypersurfaces in projective spaces. Similar to the situation above regarding signs, if one changes the signs in the expression of the determinant, e.g., to all plus signs to obtain the permanant, one arrives at a VNP-hard sequence, where VNP is Valiant's algebraic analogue of NP, see §6 for a definition.
Problem: Determine geometric properties of sequences of hypersurfaces such that their defining equations admit polynomial time evaluations.
A very tentative step towards resolving this problem is taken in §9. A second problem is: Problem: Determine geometric properties of sequences of hypersurfaces such that their defining equations are in the class VNP.
A first observation is that if a polynomial is easy to evaluate, then any specialization of it is also easy to evaluate, or in other words the polynomial associated to any linear section of its zero set is also easy to evaluate. This leads to Valiant's conjecture [36] that the permanent sequence (perm m ) cannot be realized as a linear projection of the determinant sequence (det n(m) ) unless n grows faster than any polynomial (Conjecture 7.3.3). The best results on this conjecture so far are due to T. Mignon and N. Ressayre [26] who use local differential geometry. While the local differential geometry of the det n -hypersurface is essentially understood (see Theorem 7.4.1), a major difficulty in continuing their program is to distinguish the local differential geometry of the perm m -hypersurface from that of a generic hypersurface. Furthermore, the determinant hypersurface is so special it may be difficult to isolate exactly which of its properties are the key to it having a fast evaluation. Suggestions for overcoming this second difficulty are given in §8.2.
From the geometric point of view, a significant esthetic improvement towards approaching Valiant's conjecture is the Geometric complexity theory (GCT) program proposed by K. Mulmuley and M. Sohoni in [33,34]. Instead of regarding the determinant itself, one considers its GL n 2 -orbit closure in P(S n C n 2 ) and similarly for the permanent. The problem becomes one to compare two algebraic varieties that are invariant under a group action. In §8.1 I briefly review the program, summarizing from [2]. Even with the GCT program, one still begins with the determinant and permanent, and it might be useful to consider other sequences as well, as discussed in §8.

2.
The examples up to this point indicate that sequences in VP that are not in VP e , the sequences of polynomials having "small" expressions, see §6 for a precise definition, (and analogously for P) should have some kind of symmetry, but that symmetry could be hidden. It would be very useful to be able to formalize the notion of "hidden symmetry" in this context. Similarly, it would be useful to have coordinate free definitions of complexity classes.
Overview. In §2, I describe how to convert a counting problem to a vector space pairing. In §3, I describe how the "big cell" in the Grassmannian (resp. the spinor variety) admits an interpretation as the set of vectors of minors (resp. sub-Pfaffians) in preparation for §4, where I review the reformulation of holographic algorithms of [23] and point out a consequence that all problems in NP are "nearly" holographic (Theorem 4.2.2). In §5 the results of §3 are generalized to all cominuscule varieties. In §6 I review the definitions of Valiant's complexity classes in preparation for sections 7, 8 and 9. §7 discusses Valiant's conjecture regarding the permanent as a projection of the determinant. There are two new results (Theorems 7.4.1 and 7.4.2) on the local differential geometry of the hypersurface {det n = 0} relevant for complexity. The Geometric Complexity Theory program of Mulmuley and Sohoni is very briefly reviewed in §8. In §9 a coordinate free definition of the class VP e is given, where joins and multiplicative joins play a role, the latter perhaps being defined here for the first time, and a first step is taken towards a geometric definition of VP, using the idea of possibly hidden symmetries. Other than as noted above, the various sections can be read independently.
The results presented in this paper are preliminary -the main purpose of the paper is to indicate some of the deep and beautiful connections between the P v. NP problem and geometry. For connections with other areas of mathematics, see, e.g. [47].
I use the summation convention that repeated indices appearing up and down are to be summed over their range. 2009. This paper follows up on joint work with P. Bürgisser, L. Manivel and J. Weyman on the GCT program, work with J. Morton and S. Norine on holographic algorithms, and reports on current work with L. Manivel and D. The. It is a pleasure to thank these collaborators as well as S. Kumar, L. Valiant and J. Cai for helping me understand the computer science literature and many useful discussions. The AIM workshop Geometry and representation theory of tensors for computer science, statistics and other areas July 21-25, 2008, was especially useful as a starting point for these conversations and I gratefully thank AIM and the other participants of the workshop. Finally I thank the anonymous referees for their useful suggestions.

Holographic algorithms I: Counting problems as vector space pairings
For simplicity of exposition, I restrict to the complexity problem of counting the number of solutions to equations c s over F 2 with variables x i . This problem is called #SAT in the complexity literature. (In complexity theory one usually deals with Boolean variables and clauses, which is essentially equivalent to equations over F 2 but some care must be taken in the translation.) It came as a shock to the complexity community when L. Valiant [43] showed that a certain restricted counting problem (affectionately called "#Pl-Rtw-Mon-3CNF" in the complexity literature), where counting the number of solutions mod 2 is already #P complete, had the property that counting the number of solutions mod 7 could be done in polynomial time. J. Cai [8] recognized Valiant's method could be formed in terms of pairings of tensors in dual spaces, and the discussion below follows his formulation. See §4.4 below for more on the history and further references.
To convert a counting problem to a vector space pairing, proceed as follows: Step 1. To an instance of a problem construct a bipartite graph Γ = (V x , V c , E) that encodes the problem. Here V x , V c are the two sets of vertices and E is the set of edges. V x corresponds to the set of variables, V c to the set of equations, and there is an edge e is joining the vertex of the variable x i to the vertex of the equation c s iff x i appears in c s .
Step 2. Construct "local" tensors that encode the information at each vertex. To do this first associate to each edge e is a vector space A is = C 2 with basis a is|0 , a is|1 and dual basis α is|0 , α is|1 of A * is . Next, to each variable x i associate the vector space which will encode that x i should be consistently assigned either 0 or 1 each time it appears. Now to each equation c s we associate a tensor in A * s := ⊗ {i|e is ∈E} A * is that encodes that c s is satisfied. For example, say x i , x j , x k appear in c s and that which is satisfied over α i 1 ,s|ǫ 1 ⊗ · · · ⊗ α i ds ,s|ǫ ds .
Step 3. Tensor all the local tensors from V x (resp. V c ) together to get two tensors in dual vector spaces with the property that their pairing counts the number of solutions. That is, consider G := ⊗ i g i and R := ⊗ s r s respectively elements of the vector spaces A := ⊗ e A e and A * := ⊗ e A * e . Then, the pairing G, R counts the number of solutions. Remark 2.0.1. Up until now I could have just taken each A is = Z 2 . The reason for complex numbers was to allow a larger group action. This group action will destroy the local structure but leave the global structure unchanged. Valiant's inspiration for doing this was quantum mechanics, where particles are replaced by wave functions.
So far we have replaced our original counting problem with the problem of computing a pairing A × A * → C where the dimension of A is exponential in the size of the input data. If we had arbitrary vectors, then there is no way to perform this pairing in a number of steps that is polynomial in the size of the original data. We saw that if one is lucky, the pairing can be computed quickly. In the next section I describe the geometry underlying "getting lucky" and in the following section discussion how to make local changes of bases that simultaneously put each g i and r s into spinor varieties.

Detour: Grassmannians and Spinor varieties
Mathematicians are used to viewing the Grassmannian as the variety parametrizing linear subspaces of a vector space, and the spinor variety as parametrizing isotropic subspaces. However in statistics, the "big cell" inside arises as the space parametrizing the set of minors of matrices (resp. Pfaffians of skew-symmetric matrices). We show how these second descriptions lead to the fast algorithms mentioned in the introduction.
3.1. The Grassmannian as a variety parametrizing minors of matrices. Let W be a vector space and let G(k, W ) denote the Grassmannian of k-planes through the origin in W . Assume WLOG that k ≤ dimW −k. The Plücker embedding G(k, W ) ⊂ P(Λ k W ) is obtained by, given a k-plane E, taking a basis e 1 , ..., e k of E and sending E to the point [e 1 ∧· · ·∧e k ] ∈ P(Λ k W ). The cone over the Grassmannian, The Grassmannian G(k, W ) admits a local parametrization as follows: . In what follows I will also need to work with G(k, W * ), In our dual bases, a local parametrization about . I next explain how to interpret the open subset of G(k, W ) described above as the vector of minors for E * ⊗ F .
For vector spaces E, F , Λ k (E ⊕ F ) has the following decomposition as a GL(E) × GL(F ) module: has the geometric interpretation as the space of s × s minors on E ⊗ F * , i.e., with any choices of bases, write an element f of E ⊗ F * as a matrix, then a basis of Λ s E * ⊗ Λ s F evaluated on f will give the set of s × s minors of f .
To see these minors explicitly, note that the bases of E * , F induce bases of the exterior powers. Expanding out v above in such bases, (recall that the summation convention is in use) i.e., writing v as a row vector in the induced basis: , ..., ∆ I,S (x), ..., ) where we use the notation I = (i 1 , ..., i p ) S = (s 1 , ..., s p ) and ∆ I,S (x) denotes the corresponding p × p minor of x. Similarly α = (1, y j s , y j s y i t − y i s y j t , ..., ).
Fix bases so x, y are k × (n − k) matrices. I claim because the characteristic polynomial of a product of a k × ℓ matrix t x with an ℓ × k matrix y is: While (3.1.2) is no doubt classical, I include a proof as I didn't find one in the literature.
For a linear map f : where, if one chooses a basis of A and represents f by a matrix, then the entries of the matrix representing f ∧k in the induced basis on Λ k A will be the k × k minors of the matrix of f . In particular, if dimA = a, then, f ∧a is multiplication by a scalar which is det(f ).
Recall the decomposition: To each x ∈ E * ⊗ F , y ∈ E ⊗ F * , associate the element be a volume form. All that remains to check is that when we re-order our terms that the signs work out correctly, which is left to the reader.

Spinor varieties.
For the interpretation of spinor varieties as maximal isotropic subspaces on a quadric, see any of [14,17,21]. Here I simply define the spinor variety as the Zariski closure of the set of vectors of sub-Pfaffians of a skew-symmetric matrix with variables as entries. See [20] for the connection with the classical definition.
Let E be an n-dimensional vector space equipped with a volume form. Define (Ŝ + ) 0 to be the image of the map , ..., ) =: sPf(x) as |I| varies over the even numbers from 0 to n 2 . The space of sub-Pfaffians of size 2p is parametrized by Λ 2p E. If n is even, S + is self dual, and if n is odd, its dual is S − := Λ odd E because E is equipped with a volume form, so Λ 2p E * = Λ n−2p E.
Recall the decomposition where for an even set I ⊆ [n], define σ(I) = i∈I i, and define sgn(I) = (−1) σ(I)+|I|/2 . Put more invariantly, the j-th term is the pairing For a matrix z define a matrixz by settingz i j = (−1) i+j+1 z i j . Let z be an n × n skew-symmetric matrix. Then for every even I ⊆ [n], Thus: Let z, y be skew-symmetric n × n matrices. Then sPf(z), sPf ∨ (y) = Pf(z + y).
In particular, when n is even, the pairing The first few spinor varieties are classical varieties in disguise (corresponding to coincidences of Lie groups in the first two cases and triality in the third): In particular, although the codimension grows very quickly, it is small in these cases. The next case S 5 ⊂ P 15 is not isomorphic to any classical homogeneous variety. The SL 2 C action. To try to move both G, R to special position so that the pairing can be evaluated quickly, identify all the A e with a single C 2 , and allow SL 2 C to act. This action is very cheap, and of course if we have it act simultaneously on A and A * , the pairing G, R will be unchanged. This step cannot always be carried out, otherwise Valiant would have proved P = NP.
To illustrate, we now restrict to #3SAT − N AE, which is still NP-hard.
The tensor g i corresponding to a variable vertex x i is (2.0.1). The tensor corresponding to a NAE clause r s is (2.0.2) and d s = 3 for all s. Let be the basis change, the same in each A e , sending a e|0 → a e|0 + a e|1 and a e|1 → a e|0 − a e|1 which induces the basis change α e|0 → 1 2 (α e|0 + α e|1 ) and α e|1 → 1 After this change of basis g i ∈ S #{s|e is ∈E} and r s ∈ S 4 for all i, s!
Definition 4.2.1. Let P be a counting problem. We will say that P is pre-holographic if it admits a formulation such that the vectors g i , r s are all simultaneously representable as vectors of sub-Pfaffians.
The following was proved (although not stated) in [23]: Proof. To prove the theorem it suffices to exhibit one #P complete problem that is preholographic. Counting the number of solutions to #3SAT − N AE is one such.

4.3.
What goes wrong. While for #3SAT − N AE it is always possible to give V and V * structures of the spin representations S + and S * + , so that [G] ∈ PV and [R] ∈ PV * both lie in spinor varieties, these structures may not be compatible! What goes wrong is that the ordering of pairs of indices (i, s) that is good for V may not be good for V * . The "only" thing that can go wrong are the signs of the sub-Pfaffians, see [23] for details.
In [23] we determine sufficient conditions for there to be a good ordering of indices and show that if the bipartite graph Γ was planar, then these sufficient conditions hold.

4.4.
History. In Valiant's original formulation of holographic algorithms (see [38,39,40,41,42,44]), the step of forming Γ is the same, but then Valiant replaced the vertices of Γ with weighted graph fragments to get a new weighted graph Γ ′ in such a way that the number of (weighted) perfect matchings of Γ ′ equals the answer to the counting problem. Then, if Γ ′ is planar, one can appeal to the famous FKT algorithm [19,35] to compute the number of weighted perfect matchings in polynomial time. Valiant also found certain algebraic identities that were necessary conditions for the existence of such graph fragments.
Cai [7,8,9,10,11,12,13] recognized that Valiant's procedure could be reformulated as a pairing of tensors as in steps two and three, and that the condition on the vertices was that the local tensors g i r s could, possibly after a change of basis, be realized as a vector of sub-Pfaffians. In Cai's formulation one still appeals to the existence of Γ ′ and the FKT algorithm in the last step.

Exponential pairings in polynomial time
In this section we show that the same phenomenon that we observed above for Grassmannians and spinor varieties holds for all cominuscule varieties, the homogeneous varieties that can be given the structure of a compact Hermitian symmetric space. The non-trivial cases are (where for notational convenience we use the rank of G plus one in the A n−1 = SL n -case): Explanations of V : W is a vector space of dimension n in the first case, 2n in the third, S + is the (positive) half-spin representation of Spin 2n , Λ n W = Λ n W/(Λ n−2 W ∧ ø) where ø ∈ Λ 2 W is a symplectic form. E, E j are vector spaces of dimension p in the last two cases.
Explanations of G/P : G(k, W ) denotes the Grassmannian of k-planes in its Plucker embedding, S + the "pure spinors" or spinor variety, G Lag (n, 2n) denotes the Lagrangian Grassmannian of n-planes isotropic for the symplectic form ø ∈ Λ 2 C 2n , Seg(PE 1 × · · · × PE n ) denotes the Segre product, the projectivization of the set of decomposable tensors in E 1 ⊗ · · · ⊗ E n and v n (PE) denotes the Veronese variety of the projectivization of homogeneous polynomials of degree n on E * that are n-th powers of a linear form.
Explanations of g/p: g, p are the Lie algebras of G, P . Let G 0 denote the Levi-factor of P . G 0 is respectively S(GL(E) × GL(F )), GL(E), GL(E), GL(E ′ 1 )× · · · × GL(E ′ n ), GL(E ′ ). As a G 0 -module, g/p is the tangent space to G/P at the point of G/P corresponding to Id ∈ G. I have written F = W/E. Fix vectors e j ∈ E j , e ∈ E and let ℓ j , ℓ respectively denote the lines they span, then E ′ j = ℓ 1 ⊗ · · · ⊗ ℓ j−1 ⊗ E j /ℓ j ⊗ ℓ j+1 ⊗ · · · ⊗ ℓ n and E ′ = E/ℓ. In each case g/p is a space of endomorphisms and V as a G 0 -module is the sum of the spaces of all minors (of all sizes) of g/p, except in the spinor case, where one takes all sub-Pfaffians.
It remains to prove the cases of the Lagrangian Grassmannian, the Segre and the Veronese.

5.2.
Lagrangian Grassmannian case. The Lagrangian Grassmannian G Lag (n, 2n) ∈ PΛ n W is a linear section of G(n, 2n) ⊂ PΛ n W . Here Λ n W = Λ n W/(Λ n−2 W ∧ ø) = W Sp(2n,W ) øn and the quotient may be viewed as the complement to Λ n−2 W ∧ ø ⊂ Λ n W to obtain the linear section.
The interpretation of an open subset (the "big cell") of G Lag (n, W ) is as the set of vectors of (non-redundant) minors of symmetric matrices. The symplectic form enables the identification of W/E ≃ E * and the linear subspace of The subspace of Λ j E * ⊗ Λ j E * giving rise to a non-redundant set of minors corresponds to the sub-module For the Lagrangian Grassmannian case it suffices in (3.1.3) to take

5.3.
Segre and Veronese cases. The Segre is parametrized by a map φ where in each term s 1 < · · · < s q . Let φ ∨ denote the map to the dual Segre.
Here : The Veronese is parametrized by (x j ) → (a 0 + x j a j ) p and the same matrix as above works replacing x j s with x j for all s and similarly for y.

Definitions of VP, VNP and VP e
In the discussion above, the problem presented was far removed from geometry, and it was only after significant work that geometric objects appeared. L. Valiant [36] has proposed algebraic analogs of the complexity classes P and NP in terms of sequences of polynomials. Such classes should be closer to geometry, however, the properties of the resulting sequences of hypersurfaces relevant for geometry have yet to be determined. In this expository section, I briefly review the relevant definitions.
6.1. VP e . An elementary measure of the complexity of a (homogeneous) polynomial p is as follows: given an expression for p, count the total number of additions plus multiplications present in the expression, and then take the minimum over all possible expressions. p n (x, y) = x n + nx n−1 y + n 2 x n−2 y 2 + n 3 x n−3 y 3 + · · · + y n This expression for p n involves n(n + 1) multiplications and n additions, but one can also write p n (x, y) = (x + y) n which requires n multiplications and one addition to evaluate.
Definition 6.1.2. An arithmetic circuit C is a finite, acyclic, directed graph with vertices of in-degree 0 or 2 and exactly one vertex of out degree 0. In degree 0, inputs are labelled by elements of C ∪ {x 1 , ..., x n } and in degree 2, vertices are called computation gates and labelled with + or * . The size of C is the number of vertices. From a circuit C, one can construct a polynomial p C in the variables x 1 , ..., x n .
If C is a tree (i.e., all out degrees are at most one), then the size of C equals the number of +'s and * 's used in the formula constructed from C. Definition 6.1.3. For f ∈ S d C m , the expression size E(f ) is the smallest size of a tree circuit that computes f . Define the class VP e to be the set of sequences (p n ) such that there exists a sequence (C n ) of tree circuits, with the size of C n bounded by a polynomial in n, such that C n computes p n .
It turns out that expression size is too naïve a measurement of complexity, as consider Example 6.1.1, we could first compute z = x + y, then w = z 2 , then w 2 etc... until the exponent is close to n, for a significant savings in computation when n is large.
6.2. VP, VP ws and closures. Circuits more general than trees allow one to use the results of previous calculation and gives rise to the class VP: Definition 6.2.1. The class VP is the set of sequences (p n ) of polynomials of degree d(n) in v(n) variables where d(n), v(n) are bounded by polynomials in n and such that there exists a sequence of circuits (C n ) of polynomialy bounded size such that C n computes p n .
A polynomial p(y 1 , ..., y m ) is a projection of q(x 1 , ..., x n ) if we can set x i = a s i y s + c i for constants a s i , c i to obtain p(y 1 , ..., y m ) = q(a s 1 y s + c 1 , ..., a s n y s + c n ). Geometrically, if we homogenize the polynomials by adding variables y 0 , x 0 , we can study the zero sets in projective space. Then p is a projection of q iff Zeros(p) ⊂ CP m is a linear section of Zeros(q) ⊂ CP n . This is because if we consider a projection map V → V /W , then (V /W ) * ≃ W ⊥ ⊂ V * . Definition 6.2.2. A sequence (p n ) is hard for a complexity class C defined by sequences of polynomials, if for all sequences (q m ) in C, q m can be realized as a projection of p n(m) where the function n(m) is bounded by a polynomial in m. A sequence (p n ) is complete for C if it is hard for C and if (p n ) ∈ C.
A famous example of a sequence in VP is det n ∈ S n C n 2 , despite its apparently huge expression size. While it is known that (det n ) ∈ VP, it is not known whether or not it is VP-complete. On the other hand, it is known that (det n ) is VP e -hard, although it is not known whether or not (det n ) ∈ VP e . When complexity theorists and mathematicians are confronted with such a situation, what else do they do other than make another definition? Definition 6.2.3. The class VP ws is the set of sequences (p n ) where deg(p n ) is bounded by a polynomial and such that there exists a sequence of circuits (C n ) of polynomialy bounded size such that C n represents p n , and such that at any multiplication vertex, the component of the circuit of one of the two edges coming in is disconnected from the rest of the circuit by removing the multiplication vertex.
In [25] they show (det n ) is VP ws -complete, so Conjecture 7.3.3 may be rephrased as conjecturing VP ws = VNP.
Remark 6.2.4. It is considered a major open question to determine whether or not (det n ) ∈ VP e . Definition 6.2.5. Given a complexity class C defined in terms of sequences of polynomials, we define a sequence (p n ) to be in C if there exists a curve of sequences q n,t , such that for each fixed t 0 = 0, (q n,t 0 ) ∈ C and for all n, lim t → 0 q n,t = p n . 6.3. VNP. The class VNP essentially consists of polynomials whose coefficients can be determined in polynomial time. Consider a sequence h = (h n ) ∈ C[x 1 , ..., x n ] ≤n of (not necessarily homogeneous) polynomials of the form In the naïve computation of det n with this formula, one uses (n − 1)(n!) multiplications and n! − 1 additions. Nevertheless, one has the essentially classical: Fixing bases of E, F and identifying E * ⊗ F * with the space of n × n matrices, there are subspaces of E * ⊗ F * on which det can be evaluated by performing n arithmetic operations, for example the upper-triangular matrices which we will denote by b.
det n is invariant under the action of the subgroup U ⊂ SL(E) of all upper-triangular matrices with 1's on the diagonal as well as the group W of permutation matrices in SL(E).
Proposition 7.1.1 essentially follows from: Proposition 7.1.2 (Gaussian elimination). Notations as above, given x ∈ E * ⊗ F * , there exists g in the group generated by U and W such that g · x ∈ b. Such a g can be computed by performing a number of arithmetic operations that is polynomial in n = dimE.
proof of Prop. 7.1.1. For sufficiently generic matrices the algorithm is clear and just using U is sufficient. For an algorithm that works for arbitrary matrices, see, e.g., [1,25].
7.2. The permanent. Define the permanent perm n ∈ S n (E ⊗ F ) to be the unique up to scale element of S n E ⊗ S n F ⊂ S n (E ⊗ F ) invariant under the action of the diagonal matrices and permutation matrices acting on both the left and the right (i.e. the normalizers of the tori in SL(E) × SL(F )). If x ∈ E * ⊗ F * is expressed as a matrix, then perm n (x) = σ∈Sn x 1 σ(1) , ..., x n σ(n) . In particular, any polynomial is the projection of some determinant.

Conjecture 7.3.3 (Valiant). [36]
Let dc(perm m ) be the smallest integer n such that perm m can be realized as a projection of det n . Then dc(perm m ) grows faster than any polynomial in m.
7.4. Differential invariants of det n . This subsection discusses preliminary results of work with D. The and L. Manivel. Let X ⊂ P n and Y ⊂ P m be varieties such that there is a linear space L ≃ P m ⊂ P n such that Y = X ∩ L.
Say y ∈ Y = X ∩ L. Then the differential invariants of X at y will project to the differential invariants of Y at y. A definition of differential invariants adequate for this discussion (assuming X, Y are hypersurfaces) is as follows: choose local coordinates (x 1 , ..., x n+1 ) for P n at x = (0, ..., 0) ∈ X such that T x X = ∂ ∂x 1 , ..., ∂ ∂x n and expand out a Taylor series for X: The zero set of (r 2 ij dx i • dx j , ..., r k i 1 ,...,i k dx i 1 • · · · • dx i k ) in PT x X is independent of choices. I will refer to the polynomials F ℓ,x (X) although they are not well defined individually. For more details see, e.g. [18,Chap. 3].
One says that X can approximate Y to k-th order at x ∈ X mapping to y ∈ Y if one can project the differential invariants to order k of X at x to those of Y at y.
In [26] it was shown that the determinant can approximate any polynomial to second order if n ≥ m 2 2 and that perm m is generic to order two, giving the lower bound dc(perm m ) ≥ m 2 2 . The previous lower bound was dc(perm m ) ≥ √ 2m due to J. Cai [6] building on work of J. von zur Gathen [46].
One can ask what happens at higher orders.
If X ⊂ PV is a quasi-homogeneous variety, i.e., a group G acts linearly on V and X = G · Let e 1 , ..., e n be a basis of E * and f 1 , ..., f n a basis of F * , let v = e 1 ⊗ f 1 + · · · + e n−1 ⊗ f n−1 , so [v] ∈ Zeros(det n ) and Zeros(det Write an element of T [v] Zeros(det n ) as a triple (x, A, y). In matrices, Taking the g([v])-module structure into account, it is straight-forward to show: With the notations above, there exist bases in which the differential invariants of X at [v] are the polynomials Since the permanent hypersurface is not quasi-homogeneous, its differential invariants are more difficult to calculate. It is even difficult to write down a general point in a nice way (that depends on m, keeping in mind that we are not concerned with individual hypersurfaces, but sequences of hypersurfaces). For example, the point on the permanent hypersurface chosen in [26] is not general as there is a finite group that preserves it. To get lower bounds it is sufficient to work with any point of the permanent hypersurface, but one will not know if the obtained bounds are sharp. To arrive at dc(perm m ) being an exponential function of m, one might expect to improve the exponent by one at each order of differentiation. The following theorem shows that this does not happen at order three.
The Mignon-Ressayre result implies that any hypersurface in 2n − 2 variables defined by a homogeneous polynomial can be approximated to order two at any point by an affine linear projection of {det n = 0} ⊂ C n 2 .
Theorem 7.4.2. Any hypersurface in n − 1 variables can be approximated to order three at any point by an affine linear projection of {det n = 0} ⊂ C n 2 .
In particular, {perm m = 0} ⊂ C m 2 can be approximated to order three at a general point by an affine linear projection of {det m 2 +1 = 0} ⊂ C (m 2 +1) 2 .
Proof. The rank of F 2 for the determinant is 2(n − 1), whereas the rank of F 2 for the permanent, and of a general hypersurface in q variables at a general point, is q − 2. so one would need to project to eliminate (n − 1) 2 variables to agree to order two.
Thus it is first necessary to perform a projection so that the matrix A, which has independent variables as entries becomes linear in the entries of x, y, write A = A(x, y). The projected pair F 2 , F 3 is still not generic because it has two linear spaces of dimension n − 1 in its zero set. This can be fixed by setting y = L(x) for L : C n−1 → C n−1 a linear isomorphism. At this point one has F 2 = L(x)x, F 3 = L(x)A(x, L(x))x. Take L to be the identity map, so the cubic is of the form i,j x i A ij (x)x j where the A ij (x) are arbitrary. This is an arbitrary cubic.
8. Geometric Complexity Theory approach to VP ws v. VNP In a series of papers [33,34,31,32,30,28,29,27], K. Mulmuley and M. Sohoni outline an approach to prove VP ws = VNP. Let ℓ be a linear coordinate on C, and take any linear inclusion C ⊕ C m 2 ⊂ C n 2 to have ℓ n−m perm m be a homogeneous degree n polynomial on C n 2 . Mulmuley and Sohoni observe that VP ws = VNP is equivalent to the following assertion: Let dc(perm m ) denote that the smallest value of n such that [ℓ n−m perm m ] ∈ GL n 2 · [det n ]. Then VP ws = VNP is equivalent to the statement dc(perm m ) grows faster than any polynomial: [33] dc(perm m ) grows faster than any polynomial in m.
Remark 8.0.4. Recently in [22] it was shown that dc(perm m ) ≥ m 2 2 and that there exist sequences (p m ) with dc(p m ) < dc(p m ).
In an attempt to find such a sequence of modules, Mulmuley and Sohoni consider SL n 2 · det n and SL m 2 ·perm m because on the one hand their coordinate rings can be determined in principle using representation theory, and on the other hand they are closed affine varieties. They observe that any SL n 2 -module appearing in C[SL n 2 · det n ] must also appear in C[GL n 2 · det n ] k for some k. Regarding the permanent, for n > m, SL n 2 · ℓ n−m perm m is not closed, so they develop machinery to transport information about C[SL m 2 · perm m ] to C[GL n 2 · ℓ n−m perm m ], including a notion of partial stability.
Mathematical aspects of this program are discussed in [2]. The representation-theoretic information Mumuley and Sohoni propose to exploit is studied in detail. In particular [2, Thm 5.7.1] is a precise description of conditions on Kronecker coefficients that are equivalent to Conjecture 8.1.1. In addition, suggestions are made for further geometric information that one could take into account that might imply a more tractable problem in representation theory.
The price of using SL n 2 instead of GL n 2 is that one loses the grading of the coordinate rings. On the other hand, in order to use GL n 2 , one must solve, or at least partially solve, an extension problem, which to even begin work on, means that one must determine the codimension one components of the boundaries in the orbit closures.
Remark 8.1.2. Recently in [5] evidence was given that the vanishing of Kronecker coefficients that would be necessary for Conjecture 8.1.1 is unlikely to occur. 8.2. Beyond determinant and permanent. Instead of considering det n , one could take a sufficiently generic g n ∈ GL n 2 and consider p n := det n + g n · det n . Then the subgroup G(p n ) of GL n 2 preserving p n will be the same as that for a generic polynomial, although the sequence (p n ) is still VP ws -complete. Thus just looking at the orbit, there would be fewer modules appearing in C[SL n 2 · [p n ]] than in C[SL n 2 · [perm n ]]. In particular the orbit closure is larger than that of the permanent. More generally, let r(n) be a polynomial and take a sequence of points in p n ∈ σ r(n) (GL n 2 · [det n ]), the r-th secant variety of GL n 2 · [det n ]. One could study the differential invariants of these varieties to see how they project to the permanent as in §7 and consider GCT program using the varieties GL n 2 · p n .
More examples of sequences of polynomials are given by the immanants defined by Littlewood in [24]. Immanants generalize the determinant and permanent. Given a partition π = (p 1 , ..., p r ) of n, and a vector space V of dimension at least r, let S π V denote the corresponding irreducible GL(V )-module. IM π ∈ S n C n 2 may be defined as follows: consider C n 2 = E ⊗ F , where E, F = C n . Then S n (E ⊗ F ) = ⊕ π S π E ⊗ S π F as a GL(E) × GL(F ) module. Let D E ⊂ SL(E), D F ⊂ SL(F ) denote the tori, i.e., the groups of diagonal matrices with determinant one. Let S E n , S F n denote the groups of permutation matrices acting on the left and right, and let ∆(S n ) ⊂ S E n × S F n denote the diagonal embedding. Then IM π ∈ S π E ⊗ S π F is the unique (up to scale) element acted on trivially by (D E × D F ) ⋉ ∆(S n ).
Such investigations will be the subject of future work.

Towards geometric definitions of complexity classes
As mentioned several times, symmetry, sometimes in hidden form, appears to play a central role in characterizing sequences in VP that are apparently not in VP e . To make a geometric study of complexity, it would be desirable to have coordinate free definitions. In this section I give a coordinate free and geometric definition of the class VP e . I then give a coordinate free and geometric definition of a class VP hs which is intended as a first attempt to geometrize the class VP. Unfortunately at this writing I have no idea for a proposed purely geometric definition of VNP. (S. Basu and M. Shub, in separate personal communications, have proposed that VNP should somehow be viewed as a bundle over VP, but I have been unable to make this precise.) 9.1. Joins and multiplicative joins. The join of projective varieties X 1 , ..., X r ⊂ PV , J(X 1 , ..., X r ) ⊂ PV , is the Zariski closure of the points of the form [p 1 + · · · + p r ] with [p j ] ∈ X j . The expected dimension of J(X 1 , ..., X r ) is min( dimX j + r − 1, dimPV ). LetT [p] X ⊂ V denote the affine tangent space of X at [p] ∈ X. Terracini's lemma says that if ([p 1 ], ..., [p r ]) ∈ X 1 × · · · × X r is a general point, thenT [p 1 +···+pr] J(X 1 , ..., X r ) =T [p 1 ] X 1 + · · · +T [pr] X r . One can similarly define joins in affine space. The expressions are the same without the brackets.  Similarly, let A d,v denote the space of all polynomials of degree at most d in v variables. For affine varieties X ⊂ A d 1 ,v , Y ⊂ A d 2 ,v , M J(X, Y ) ⊂ A d 1 +d 2 ,v is defined in the same way without brackets.
Proof. Let p j (t) be a curve in X j with p j (0) = p j . Differentiate the expression p 1 (t) • · · · • p r (t) at t = 0 to get the result. Question 9.1.3. What are the degenerate multiplicative joins, i.e., those that fail to be of the expected dimension? 9.2. A geometric characterization of VP e . Recall that the expression size E(p) of a polynomial p ∈ A d,v is given by the number of internal nodes of the smallest tree circuit computing p. Define E(p) to be the smallest integer such that there is a curve p t with lim t → 0 p t = p 0 and such that E(p t ) = E(p) for t = 0. By definition, a sequence (p n ) ∈ A d(n),v(n) is in VP e (resp. VP e ) if there exists a polynomial r(n) such that E(p n ) ≤ r(n) (resp. E(p n ) ≤ r(n).).
To a tree circuit Γ associated to a polynomial p, associate an algebraic variety as follows: first form an new tree circuit Γ ′ by collapsing all pairs of input nodes that are joined by a + to a single input node, and repeat as many times as necessary until no pairs of input nodes are joined by a +. (I take this first step to eliminate the choice of coordinates involved in making the circuit.) Associate to each input node a copy of PV .
Thus on Γ ′ , if any two input nodes are joined, they are joined by a * -node. Now perform a step by step procedure to eliminate all * -nodes joining pairs of input nodes. Take a * -node joined to two input nodes, and form a subtree containing all other * -nodes joined to it and an input node. Say there are j 1 − 1 such. Record the variety M J j 1 := M J(PV, ..., PV ) of j 1 copies of PV . Collapse the subtree to a single input node and associate M J j 1 to this input node. Now start again, say we arrive at j 2 −1 nodes in the subtree and record the variety M J j 2 = M J(PV, ..., PV ) of j 2 copies of PV . Continue until we have recorded p varieties of multiplicative joins of V of various sizes.
We arrive at a new graph Γ ′′ all of whose p input nodes have varieties M J j i associated to them and when input nodes are paired together by an internal node, the node is a +-node. Now perform a step by step procedure to eliminate all +'s joining pairs of input nodes. Take the first +, say that the variety M J j i 1 is one of the input nodes and form a subtree consisting of all other +'s joined to it. Say there are k − 1 such. Record the variety J(M J j i 1 , ..., M J j i k ). Collapse the subtree to a single input node and associate J(M J j i 1 , ..., M J j i k ) to this input node. Continue until we have varieties of joins of multiplicative joins of various sizes as our new input nodes with all pairings of input nodes * -nodes. Now continue as we did with Γ ′ , taking multiplicative joins (of the joins of multiplicative joins) until the further collapsed graph has all pairings of input nodes +'s, then go back to taking joins etc... This process terminates after a number of steps fewer than the number of nodes of Γ, and one arrives at a variety Σ Γ of successive joins and multiplicative joins. By construction p ∈ Σ Γ .
Note that for each such variety, there are many Γ that are associated to it, but each has, up to the initial v times the number of initial input nodes, the same expression size.
Let Σ d,v R denote the union of all the varieties obtainable from a graph of at most R internal nodes computing an element of A d,v . There is a finite number of such, so Σ d,v R is an algebraic variety. The above discussion implies Theorem 9.2.1. Let p n ∈ A d(n),v(n) be a sequence with d, v polynomials. Then (p n ) ∈ VP e iff there exists a polynomial R(n) and p n ∈ Σ d(n),v(n) R(n) . In other words the complexity class VP e is characterized by a sequence of algebraic varieties.
Remark 9.2.2. One has to use the class VP e instead of VP e because when taking joins one must include limits. It is not necessary to include limits when taking multiplicative joins.