Geometric complexity theory, P vs. NP and explicit obstructions. (English) Zbl 1046.68057
Musili, C. (ed.) et al., Advances in algebra and geometry. Proceedings of the international conference on algebra and geometry, Hyderabad, India, December 7–12, 2001. New Delhi: Hindustan Book Agency (ISBN 81-85931-36-4/hbk). 239-261 (2003).
Summary: Theory of computing has given rise to some fundamental mathematical problems, notably the \(\text{P}\neq\text{NP}\) conjecture, and the related lower bound problems concerning formula or circuit size. We develop an approach to these problems through geometric invariant theory. The goal of this approach is to reduce the hard nonexistence problems under consideration to tractable existence problems.
Accordingly, we reduce the arithmetic (characteristic 0) version of the \(\text{P}\neq\text{NP}\) conjecture, and other related lower bound problems to proving existence of obstructions. These are representations in the homogeneous coordinate rings of orbit-closures in geometric invariant theory, of a class of points which are partially stable and whose stabilizers have special representation-theoretic properties. However, the Lutia-Vust complexity of these orbit closures is quite high, in contrast with the well-understood homogeneous or almost-homogeneous-spaces such as G/P, toric varieties, and spherical embeddings, whose Luna-Vust complexity is zero.
We take a step towards explicit construction of obstructions by proving two results regarding these orbit closures. The first is a generalization of the Borel-Weil theorem for G/P to these orbit-closures. Second, we coujecture a nice representation-theoretic set of generators for their ideals, and prove a weaker version of the conjecture. Such a set of generators had earlier been given for the ideal of G/P by Lakshmibai, Seshadri, Littelmann and Kostant.
Finally, using these results, we reduce, in essence the arithmetic non-existence problems under consideration to fundamental existence and construction problems in representation theory and algebraic geometry that are conjectured to be in the complexity class P.
For the entire collection see [Zbl 1015.00017].
Accordingly, we reduce the arithmetic (characteristic 0) version of the \(\text{P}\neq\text{NP}\) conjecture, and other related lower bound problems to proving existence of obstructions. These are representations in the homogeneous coordinate rings of orbit-closures in geometric invariant theory, of a class of points which are partially stable and whose stabilizers have special representation-theoretic properties. However, the Lutia-Vust complexity of these orbit closures is quite high, in contrast with the well-understood homogeneous or almost-homogeneous-spaces such as G/P, toric varieties, and spherical embeddings, whose Luna-Vust complexity is zero.
We take a step towards explicit construction of obstructions by proving two results regarding these orbit closures. The first is a generalization of the Borel-Weil theorem for G/P to these orbit-closures. Second, we coujecture a nice representation-theoretic set of generators for their ideals, and prove a weaker version of the conjecture. Such a set of generators had earlier been given for the ideal of G/P by Lakshmibai, Seshadri, Littelmann and Kostant.
Finally, using these results, we reduce, in essence the arithmetic non-existence problems under consideration to fundamental existence and construction problems in representation theory and algebraic geometry that are conjectured to be in the complexity class P.
For the entire collection see [Zbl 1015.00017].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 14L24 | Geometric invariant theory |
| 20G05 | Representation theory for linear algebraic groups |
