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 ( [e-mail]) is a professor of computer science at the university of Chicago, Il.

© 2012 aCM 0001-0782/12/06 $10.00