• No results found

Geometric Complexity Theory

N/A
N/A
Protected

Academic year: 2022

Share "Geometric Complexity Theory"

Copied!
46
0
0

Loading.... (view fulltext now)

Full text

(1)

Geometric Complexity Theory

Milind Sohoni1

An approach to complexity theory via

Geometric Invariant Theory.

Research Institute for Mathematical Sciences Kyoto University

(2)

Talk Outline

Mainly Valiant

Mainly stability and obstructions Mainly Representations

Largely hard

(3)

The satisfiability problem

Boolean variables x1, . . . ,xn

Term t1 = (¬x1∨x3∨x7), and so on upto tm. Formula t1∧t2∧. . .∧tm

Question: Decide if there is a satisfying assignment to the formula.

No known algorithm which works in time polynomial inn and m.

The problem belongs to an equivalence class called NP-completeproblems.

The question of P v. NP asks:

I Either produce an efficient algorithm.

I Or prove none exists.

This has been an outstanding question for the last 50

(4)

Decision vs. Counting

Equivalence: Solve One ⇔ Solve All Unsolvable One⇔ Unsolvable All

Many relatives ofP v. NP. We look at the counting version.

Boolean variables x1, . . . ,xn

Term t1 = (¬x1∨x3∨x7), and so on upto tm. Formula t1∧t2∧. . .∧tm

Question: Decide if there is a satisfying assignment to the formula.

Harder Question: Count the number of satisfying assignments.

Thus we have thedecision problem and its counting version.

(5)

Matchings

Question: Given a bipartite graph onn,n vertices, check if the graph has a complete matching.

This problem has a known polynomial time algorithm.

Harder Question: Count the number of complete matchings.

There is no known polynomial time algorithm to compute this number.

Even worse, there is no proof of its non-existence.

Thus, there are decision problems whose counting versions are hard.

(6)

The permanent

If X is an n×n matrix, then thepermanent function is:

permn(X) = X

σ

Y

i

xi,σ(i)

The relationship with the matching problem is obvious. WhenX is 0-1 matrix representing the bipartite graph, then perm(X) counts the number of matchings.

There is no known polynomial time algorithm to compute the permanent, and worse,no proof of its non-existence.

The function permn is #P-complete. In other words, it is the hardest counting problem whose decision version is easy to solve.

(7)

Our Thesis

Non-existence of algorithm =⇒ existence of a mathematical structure (obstructions)

These happen to arise in the GIT and Representation Theory of Orbits.

Example

Hilbert Nullstellensatz: Either polynomials f1, . . . ,fn have a common zero, or there are g1, . . . ,gn such that

f1g1+. . .+fngn= 1

Thusg1, . . . ,gn obstructf1, . . . ,fn from having a common zero.

(8)

Computation Model-Formula Size

Letp(X1, . . . ,Xn) be a polynomial.

Aformula is a particular way of writing it using ∗ and +.

formula = formula*formula | formula+formula

Thus the same function may have different ways of writing it.

The number of operations required may be different.

Example:

a3−b3 = (a−b)(a2+a∗b+b2).

Van-der-Monde (λ1, . . . , λn) =Q

i6=ji −λj).

Formula size: the number of ∗and + operations.

(9)

Formula size

A formula gives a formula tree.

This tree yields an algorithm which takes time proportional to formula size.

3 a

a b b

* *

*

3a −b 2 2

Does permn have a formula of size polynomially bounded in n?

(This also implies a polynomial time algorithm)No Answer Valiant’s construction: converts the tree into a determinant.

(10)

Valiant’s Construction

If p(Y1, . . . ,Yk) has a formula of size m/2 then,

There is aninductively constructed graph Gp with atmost m nodes, with edge-labels as (i) constants, or (ii) variable Yi. The determinantdet(Ap) of the adjacency matrix ofGp equalsp.

s1 s2

t2 t1

s

t s

t y

1 s

t

(11)

The Matrix

In other words:

p(Y1, . . . ,Yk) = detm(A) whereAij(Y) is a degree-1 expression on Y. For our example, we have:

y 1 s

t A=

0 1 0 0 1 y 1 0 0

det(A) = y

Note that in Valiant’s constructionAij =Yr or Aij =c.

formula size =m/2 =⇒ p(Y) =detm(A)

(12)

The homogenization

Lets homogenize the above construction:

Add an extra variableY0.

Letpm(Y0, . . . ,Yk) be the degree-m homogenization of p.

Homogenize theAij using Y0 to A0ij. We then have: pm(Y0, . . . ,Yk) = detm(A0) For our small example:

A=

0 1 0 0 1 y 1 0 0

 A0 =

0 y0 0 0 y0 y y0 0 0

 det(A0) =y02y

(13)

Valiant-conclusion

If a formp(Y) has a formula of size m/2 then There is anm×m-matrixAwith linear entries

det(A) =p(Y)

There is anm×m-matrixA0 with homogeneous linear entries det(A0) = pm(Y)

wherepm is them-homogenization of p.

(14)

The

hom

LetX ={X1, . . . ,Xr}.

For two formf,g ∈Symd(X), we say that f hom g, if f(X) =g(B·X)) where B is a fixed r ×r-matrix.

Note that:

B may even be singular.

hom is transitive. LinearX’form

Program for g(X)

(y) (x)

O O’

Program for f(Y)

If there is an efficient algorithm to compute g then we have such for f as well.

(15)

The insertion

Suppose thatpermn(Y) has a formula of size m/2. How is one to interpret Valiant’s construction?

LetY be n×n.

Build a largem×m-matrixX. Identify Y as its submatrix.

Y X n

m

(16)

The ”inserted” permanent

Form>n, we construct a new function permnm ∈Symm(X).

LetY be the principal n×n-matrix ofX. permmn =xmmm−npermn(Y)

Y X n

m

Thuspermn has been insertedinto Symm(X), of which detm(X) is a special element.

formula of size m/2 implies

permn=detm(A) Use xmm as the homogenizing variable

Conclusion permmn =detm(A0)

permmn hom detm

(17)

The ”inserted” permanent

Form>n, we construct a new function permnm ∈Symm(X).

LetY be the principal n×n-matrix ofX. permmn =xmmm−npermn(Y)

Y X n

m

Thuspermn has been insertedinto Symm(X), of which detm(X) is a special element.

formula of size m/2 implies

permn=detm(A) Use xmm as the

Conclusion permmn =detm(A0)

permmn hom detm

(18)

Group Action and

hom

LetV =Symm(X). The groupGL(X) acts on V as follows. ForT ∈GL(X) and g ∈V

gT(X) = g(T−1X) Two notions:

The orbit: O(g) = {gT|T ∈SL(X)}.

The projective orbit closure

∆(g) =cone(O(g)).

If f hom g then f =g(B ·X), whence

IfB is full rank thenf is in the GL(X)-orbit of g. If not, then B is

approximated by elements of GL(X).

Thus, in either case,

f hom g =⇒ f ∈∆(g)

(19)

The ∆

Thus, we see that if permn has a formula of size m/2 then permmn ∈∆(detm).

On the other hand,permmn ∈∆(detm) implies that for every >0, there is a T ∈GL(X) such that k(detm)T −permmnk< . This yields a poly-time approximation algorithm for the

permanent

Thus, we have an almost faithful algebraization of the formula size construction.

(20)

The Obstruction and its existence

To show thatperm5 has no formula of size 20/2, it suffices to show:

perm5206∈∆(det20) In other words:

V is a GL(X)-module.

f and g are special points.

What is thewitness to f 6∈∆(g)?

It is clear that such witnesses orobstructions exist in the coordinate ringk[V].

Real Question: How do I find this family and prove that it is indeed so.

(21)

The Obstruction

So letg,f ∈V =Symd(X). How do we show that f 6∈∆(g).

Exhibit a homogeneous polynomial µ∈Symr(V) which vanishes on ∆(g) but not on f.

Thisµ is then the required obstruction. We would need to show that:

µ(f)6= 0.

µ(gT) = 0 for all T ∈SL(X).

Check µon every point of Orbit(g)

False start: Use the SL(X)-invariant elements of Symr(V) for constructing such a µ.

(22)

Invariants

V is a space with a group G acting on V. Orbit(v) = {g.v|G ∈G}.

Invariant is a functionµ:V →C which isconstant on orbits.

Existence and constructions of invariants has been an enduring interest for over 150 years.

Example:

V is the space of all m×m-matrices.

G =GLm and g.v =gvg−1.

Invariants are the coefficients of the characteristic polynomial.

(23)

Invariants and orbit separation

To show that f 6∈∆(g)

Exhibit a homogeneousinvariant µwhich vanishes ong but not on f. Thisµ would then be the desired obstruction.

Easy to check if a form is an invariant.

Easy to construct using age-old recipes.

Easy to check that µ(g) = 0 and µ(f)6= 0.

µ(g) = 0 =⇒ µ(gT) = 0 =⇒ µ(∆(g)) = 0

Important Fact

If g and f are stable and f 6∈∆(g), then there is a homogeneous invariantµ such thatµ(g)6=µ(f).

(24)

Stability

g is stable iff SL(X)-Orbit(g) is Zariski-closed in V.

Most polynomials are stable.

It is difficult to show that a particular form is stable.

Hilbert : Classification of unstable points.

For matrices under conjugation, precisely the diagonalizable matrices are stable.

permm and detn are stable.

Proof:

Kempf’s criteria.

Based on the stabilizers of the determinant and

(25)

Rich Stabilizers

The stabilizer of the determinant:

The form detm(X):

I X →AXB

I X →XT detm ∈Symm(X) determinedby its stabilizer.

The stabilizer of the permanent:

The form permm(X):

I X →PXQ

I X →D1XD2

I X →XT permm ∈Symm(X) determined by its stabilizer.

Tempting to conclude that the homogeneous obstructing invariant µ now exists.

(26)

The Main Problem

Recall we wish to show permmn 6∈∆(detm) where

permmn =xmmm−nperm(Y).

permmn is unstable, in fact in the null-cone, for very trivial reasons.

Added an extra degree equalizing variable.

Treated as a polynomial in a larger redundant set of variables.

Y X n

m

(27)

Two Questions

Thus every invariant µwill vanish on permmn. There is no invariantµ such thatµ(detm) = 0 and µ(permnm)6= 0.

Homogeneous invariants will never serve as obstructions. They dont even enter the null-cone

Two Questions:

Is there any other system of functions which vanish on ∆(detm)?

Can anything be retrieved from the superficial instability of permmn?

(28)

Part II

Is there any other system of functions which vanish on ∆(detm)?

Yes. The admissibility argument.

Can anything be retrieved from the superficial instability of permmn?

Yes. Partial or parabolic stability.

Two key focal points:

Representations as obstructions

(29)

Question 1

Is there any other system of functions which vanish on ∆(detm) and enter the null-cone?

We use the stabilizer H ⊆SL(X) ofdetm.

For a representation Vλ of SL(X), we say that Vλ is

H-admissible iffVλ|H contains the trivial representation 1H. Forg stable:

Fact: k[Orbit(g)]∼=k[G/H]∼=P

λH-admissiblenλVλ Thankfully: k[∆(g)]∼=P

λH-admissiblemλVλ

Thus a fairly restricted class of G-modules will appear in k[∆(g)].

We use this to generate some elements of the ideal for ∆(g).

(30)

G and H

Consider next theG-equivariant surjection:

φ:k[V] →k[∆(g)]

We see that (i)φ is a graded surjection, and (ii) if Vµ⊆k[V]d is not H-admissible, then Vµ∈ker(φ).

Let ΣH be the ideal generated by such Vµ within k[V].

Clearly ΣH vanishes on ∆(g).

How good is ΣH?

(31)

The Local Picture

G-separability: We say that H ⊆G isG-separable, if for every non-trivialH-module Wα such that:

Wα appears in some restriction Vλ|H.

then there exists a H-non-admissible Vµ such that Vµ|H containsWα.

Theorem: Let g and H be as above, with (i)g stable, (ii) g only vector in V with stabilizerH, and (iii) H isG-separable. Then for an open subsetU of V, U∩∆(g) matches (k[V]/ΣH)U.

(32)

Applying this ...

The conditions: (i) stability of g, (ii)VH =<g > and (iii) G-separability of H.

detm and permn satisfy conditions (i) and (ii) above.

Forn = 2, stabilizer of det2 is indeed SL4-separable.

ForV =Vd

and g the highest weight vector, ∆(g) is the grassmanian. For this ΣH generates the ideal.

Forg =detm, the data ΣH does indeed enter the null-cone.

Still open:

Look atH =SLn×SLn sitting inside G =SLn2. Is H G-separable?

Does Σ determine ∆(det )?

(33)

To conclude on Question 1

Stabilizer yields a rich set ΣH of relations vanishing on ∆(detm).

GivenG-separability, ΣH does determine ∆(detm) locally.

Now suppose that permmn ∈∆(detm) then:

Look at the surjectionk[∆(detm)]→k[∆(permnm)].

Vµ ⊆k[∆(permnm)] andVµ non-H-admissible, thenVµ is therequired obstruction.

If k[∆(permnm)] is understood then this sets up the representation-theoretic obstruction.

(34)

Question 2-Partial Stability

Can anything be retrieved from the superficial instability of permmn?

Let’s consider the simpler function f = perm(Y)∈Symn(X), i.e., withuseful

variables Y and useless X −Y.

Let parabolic P ⊆GL(X) fix Y. P =LU, with U the unipotent radical.

Y X n

m

We see that:

f is fixed by U. f is L-stable.

(35)

The form f

Recallf =perm(Y)∈V =Symn(X) and P fixing Y.

We see thatf is partially stable with R =L=GL(Y)×GL(X −Y).

WithW =Symn(Y), we have the P-equivariant diagrams:

W →ι V

↑ ↑

W(f) →ιV(f)

k[W]d ι

← k[V]d

↓ ↓

k[∆W(f)]d ι

← k[∆V(f)]d

where ∆W(f) is the projective closure of the GL(Y)-orbit of f, and

V(f) is that of the GL(X)-orbit of f.

(36)

The Theorem

Lifting

TheGL(X)-module Vµ(X) occurs in k[∆V(f)]d∗ iff (Vµ(X))U is non-zero. Thus the GL(Y)-module Vµ(Y) must exist.

Next, the multiplicity ofVµ(X) in k[∆V(f)]d∗ equals that of Vµ(Y) in k[∆W(f)]d∗].

Now recall thatf =permm(Y), and let K =stabilizer(f)⊆GL(Y).

Butf is GL(Y)-stable, and

the GL(Y)-modules which appear in k[∆W(f)]d must be K-admissible.

(37)

The Grassmanian

ConsiderV =V1k(Cm) =Vk

(Cm) and the highest weight vector v. v is stable for theGLk ×GLm−k action.

V(v) is just the grassmanian.

v is partially stable with the obviousP.

W =Ck ⊆Cm and ∆W(v) is the line through v. whence

k[∆W(v)] =X

d

C

The above theorem subsumes theBorel-Weil theorem:

k[∆V(v)]∼=X

d

Vdk(Cm)

(38)

The general partially stable case

Recall: Let V be aG-module. Vector v ∈V is called partially stable if there is a parabolicP =LU and a regular R ⊆L such that:

v is fixed by U, and v isR-stable.

In the general case, there is aregular subgroup R ⊆L, whence the theory goes through

W(v)→∆Y(v)→∆V(v)

The first injection goes through a Pieri branching rule.

The second injection follows the lifting theorem.

(39)

In Summary

In other words, the theory of partially-stable ∆V(f) lifts from that of the stable case ∆W(f).

The Obstruction

LetH ⊆GL(X) stabilize detm and K ⊆GL(Y) stabilize permnm. The representation-theoretic obstruction Vµ(X) for

permmn ∈∆(detm)

Vµ is such that Vµ(X)U is non-zero.

Vµ(Y,y)|R has a K-fixed point.

Vµ(X)|H does not have a H-fixed point.

(40)

Philosophically-Two Parts

Identifying structures where obstructions are to be found.

Actually finding one and convincing others.

Two different types of problems:

Geometric

I Is the ideal of ∆(g) determined by representation theoretic data.

I Does ΣH generate the ideal of ∆(g)?

I Is the stabilizerH of g,G-separable?

F Larsen-Pink: do multiplicities determine subgroups?

Representation Theoretic

(41)

The subgroup restriction problem

Given aG-module V, doesV|H contain 1H? Given anH-module W, does V|H contain W?

The Kronecker Product ConsiderH =SLr ×SLs →SLrs =G, when does Vµ(G) contain an H-invariant?

This, we know, is a very very hard problem. But this is what arises (with r =s =m) when we consider detm.

(42)

Another problem-Strassen

Links invariant theory to computational issues.

Consider the 2×2 matrix multiplication AB =C. To compute C, we seem to need the 8 bilinear forms aijbjk.

Can we do it in any fewer?

A bilinear form onA,B is rank 1 if its matrix is of rank 1. Let S denote the collection of all rank 1 forms.

LetSk =S +S +. . .+S (k times). These are the so called secant varieties.

Strassen showed thatS7 contains all the above 8 bi-linear forms.

Consequence

(43)

Specific to Permanent-Determinant

Negative Results

von zur Gathen: m>c·n

I Used the singular loci ofdet and perm.

I Combinatorial arguments.

Raz: m>p(n), but multilinear case.

Ressayre-Mignon: m >c ·n2

I Used the curvature tensor.

For a pointp ∈M, hyper-surface κ:TPm →TPm. For any point ofdetm, rank(κ(detm))≤m.

For one point ofpermn, rank(κ(permn)) =n2. A section argument.

(44)

Any more geometry?

Is there any more geometry which will help?

The Hilbert-Mumford-Kempf flags: limits for affine closures.

I Extendable to projective closures?

I Something there, but convexity of the optmization problem breaks down.

The Luna-Vust theory: local models for stable points.

I Extendable for partially stable points?

I A finite limited local model exists, but no stabilizer condition seems to pop out.

(45)

In Conclusion

Complexity Theory questions and projective orbit closures.

I stable and partially stable points.

I obstructions obstruction existence

I Representations as obstructions

I Distinctive stabilizers

I local definability ofOrbit(g) partial stability

I lifting theorems

subgroup restriction problem

I tests for non-zero-ness of group-theoretic data

(46)

Thank you.

References

Related documents

 There is no significant effect of vestibular stimulation in improving balance for children with Down syndrome.  There is no significant effect of Neurodevelopmental therapy

In the histopathological study there was no changes seen in Heart, Lung, Liver, Spleen, and Kidney in control and drug treated groups. This result shows there is

The cues to action which modifies and influences the adult females perception is the structured teaching programme regarding cervical cancer which explains the meaning,

One of the Invited Speakers at the Complexity and Coding workshop at the Institute for Mathematics and its Applications, University of Minnesota... 40 lakhs

Jitendra Kumar, student of Dayalbagh Educational Institute, Agra completed a 6-week Internship Programme under Hankernest Technologies Pvt.. As part-fulfillment of the

But since it has been shown above that there are no significant differences between the sexes in the immature state and as it is also known that there is increased growth

5 Professor Haroon khan saheb Sunni Wakf for the Ward No.3 2 Malgies situated at University Mustafa Wakf Private Monthly - (1) 3-5- 6 Sri Ghulam Dastagir Fazil. Advocate

Los Angeles Metro is an example of a transit agency that chose this approach, positioning its new Orange Line, the city’s first BRT corridor, as an extension of its existing Metro