this efficient construction right from
the beginning. This allows us to use
the theory of algorithms—the main
tool of complexity theory—in the study
of the fundamental lower bounds.
Indeed, it is unrealistic to expect that
we can prove P ≠ NP without understanding the complexity class P and
the theory of algorithms in depth first,
as the flip strategy suggests.
The situation here may be compared to that for the well-known four
color theorem.
2 In principle, this theorem may be proved nonconstructively.
Yet, the fact remains that all known
proofs of this theorem are explicit in
the sense that they also yield efficient
algorithms for finding a four coloring
as a byproduct. The flip theorem suggests that the story of the fundamental
hardness conjectures in complexity
theory may be similar.
In this sense, these conjectures are
fundamentally different from other
conjectures in mathematics such as
the Riemann Hypothesis. Since there
is no analogous flip theorem for the
Riemann Hypothesis, it may have a
nonconstructive proof that gives no
hint on how to test efficiently if the n-th
zero of the Riemann zeta function lies
on the critical line.
is algebraic geometry necessary?
According to Valiant,
29 the arithmetic
permanent vs. determinant conjecture over Z is implied by the P vs. NC
conjecture. By the strong flip theorem,
21, 23
stronger forms of the fundamental hardness and derandomization
hypotheses in the arithmetic setting
imply an analogue of FH in algebraic
geometry of comparable difficulty. We
have already argued on the basis of
these results as to why it is not pragmatic to avoid algebraic geometry, even
though it is not formally necessary.
Another concrete evidence for the
power of algebraic geometry even in the
Boolean setting is provided by the proof
of the special case of the P ≠ NC con-
jecture.
18 It has to be emphasized here
that, unlike the earlier lower bounds
in the algebraic model,
6 this lower
bound is Boolean, not algebraic. This is
because it is in terms of the bit length
of the input, though the PRAM model
in Mulmuley18 does not allow bit opera-
tions. At present, to our knowledge,
this is the only nontrivial implication
of a fundamental hardness conjecture
that can be proved unconditionally in
a natural and realistic model of com-
putation. If we cannot prove even this
easier implication of the P ≠ NC conjec-
ture by elementary techniques, it seems
unrealistic to expect that we can prove
the far harder P ≠ NC (or NP) conjecture
by elementary techniques.
When can we expect a hard lower
bound?
The modest lower bounds based on
GCT and the earlier modest lower
bounds3, 6 are separated from the fundamental hardness conjectures that
are at least as hard as derandomization by the circle of self-referential difficulty, see Figure 3. To break into this
circle, we have to show that P contains
formidable explicit construction problems in algebraic geometry and representation theory, such as the ones that
arise in the strong flip theorem or FH.
By the law of conservation of difficulty
based on the strong flip theorem, comparable understanding of P is needed
in any approach. Unfortunately, our
current understanding of P is very
modest. Until we understand P (the
theory of algorithms) and geometry in
the required depth, we may not expect
any further lower bounds that are fundamentally different from the modest
lower bounds discussed previously.
Conclusion
GCT has broken the circle of self-reference around the fundamental hardness
conjectures in the arithmetic setting
and, in the process, has revealed deep
explicit construction and positivity
problems at the crossroads of algebraic
geometry, representation theory, and
complexity theory hidden underneath
the fundamental hardness conjectures
in complexity theory. Given the formidable nature of these problems, this is
undoubtedly only the beginning.
Acknowledgments
The author is grateful to Josh Grochow,
Jimmy Qiao, Janos Simon, and the referees for helpful comments. The work
on this paper was supported by NSF
grant CCF-1017760.
References
1. agrawal, M. Proving lower bounds via pseudo-random
generators. In Proceedings of the FS TTCS (2005),
springer-Verlag, berlin, Germany, 92–105.
2. appel, k., Haken, W., koch, J. every planar map is
four colourable. Illinois J. Math. 21 (1977), 439–567.
3. arora, s., barak, b. Computation Complexity: a Modern
approach, Cambridge university Press, Cambridge,
england, 2009.
4. blasiak, J., Mulmuley, k., sohoni, M. Geometric
complexity theory IV: nonstandard quantum group
for the kronecker problem. cs. ArXiv preprint cs.
CC/0703110 (2011).
5. boppana, r., sipser, M. the complexity of finite functions.
Handbook of Theoretical Computer Science. J. van
leeuwen, ed. Volume a, MIt press, 1990, 757–804.
6. bürgisser, P., Clausen, M., shokrollahi, M. algebraic
Complexity theory, springer-Verlag, 1997.
7. bürgisser, P. and Ikenmeyer, C. Geometric
complexity theory and tensor rank. arXiv:1011.1350
v1 (2010).
8. bürgisser, P., landsberg, J., Manivel, l., Weyman, J.
an overview of mathematical issues arising in the
geometric complexity theory approach to VP ≠ VNP.
arXiv: 0907.2850v1 [cs. CC] (2009).
9. Cook, s. the complexity of theorem-proving
procedures. In Proceedings of the third annual ACM
Symposium on Theory of Computing (1971), aCM,
new york, ny, 151–158.
10. deligne, P. la conjecture de weil II. Publ. Math. Inst.
Hau. Étud. Sci. 52 (1980), 137–252.
11. Fortnow, l. the status of the P versus nP problem.
CACM 52, 9 (2009), 78–86.
12. kabanets, V., Impagliazzo, r. derandomizing
polynomial identity tests means proving circuit lower
bounds. Comput. Complex. 13 (2004), 1–46.
13. karp, r. reducibility among combinatorial problems.
Complexity of Computer Computations. r. Miller
and J. thatcher, eds. Plenum Press, new york, 1972,
85–103.
14. landsberg, J., Manivel, l., ressayre, n. Hypersurfaces
with degenerate duals and the geometric complexity
theory program. arXiv:1004.4802 v1 [math. AG] (2010).
15. levin, l. universal sequential search problems. Probl.
Inform. transm. 9 (1973), 115–116.
16. Mignon, t., ressayre, n. a quadratic bound for the
determinant and permanent problem. Int. Math. Res.
Not.
79 (2004), 4241–4253.
17. Mulmuley, k. Geometric Complexity Theory IX.
technical report, under preparation.
18. Mulmuley, k. lower bounds in a parallel model
without bit operations. SIAM J. Comput. 28, 4 (1999),
1460–1509.
19. Mulmuley, k. Geometric Complexity Theory VII:
Nonstandard Quantum Group for the Plethysm
Problem. technical report tr-2007-14, Computer
science department, the university of Chicago, 2007.
20. Mulmuley, k. Geometric Complexity Theory VIII:
On Canonical Bases for the Nonstandard Quantum
Groups. technical report tr 2007-15, Computer
science department, the university of Chicago, 2007.
21. Mulmuley, k. explicit proofs and the flip.
arXiv:1009.0246 v1 [cs. CC] (2010).
22. Mulmuley, k. Geometric Complexity Theory VI: The
Flip via Positivity. technical report, the Computer
science department, the university of Chicago, 2010.
23. Mulmuley, k. on P vs. nP and geometric complexity
theory. JACM 58, 2 (2011).
24. Mulmuley, k., narayanan, H., sohoni, M. Geometric
complexity theory III: on deciding nonvanishing
of a littlewood–richardson coefficient. J. Algebr.
Combinator. (nov. 2011), 1–8.
25. Mulmuley, k., sohoni, M. Geometric complexity
theory I: an approach to the P vs. NP and
related problems. SIAM J. Comput. 31, 2 (2001),
496–526.
26. Mulmuley, k., sohoni, M. Geometric complexity theory
II: towards explicit obstructions for embeddings
among class varieties. SIAM J. Comput. 38, 3 (2008),
1175–1206.
27. razborov, a. lower bounds on the monotone
complexity of some boolean functions. Dokl. Akad.
Nauk SSSR 281 (1985), 798–801.
28. strassen, V. rank and optimal computation of generic
tensors. Lin. Algebra Appl. 53 (1983), 645–685.
29. Valiant, l. the complexity of computing the
permanent. TCS 8 (1979), 189–201.
30. Weyl, H. Classical Groups, Princeton university Press,
Princeton, nJ, 1946.
Ketan D. Mulmuley ( mulmulay@cs.uchicago.edu) is
a professor of computer science at the university of
Chicago, Il.
© 2012 aCM 0001-0782/12/06 $10.00