Mulmuley–Sohoni program
Generated by GPT-5-miniExpansion Funnel Raw 71 → Dedup 0 → NER 0 → Enqueued 0
| Mulmuley–Sohoni program | |
|---|---|
| Name | Mulmuley–Sohoni program |
| Also known as | GCT |
| Field | Theoretical computer science |
| Main subjects | Complexity theory, Algebraic geometry, Representation theory |
| Notable people | Ketan Mulmuley, Milind Sohoni |
| Established | 2001 |
Mulmuley–Sohoni program is a research initiative proposing an approach to the P versus NP problem and related separation problems using ideas from algebraic geometry, representation theory, and invariant theory. The program frames complexity class separations as obstructions in the setting of Geometric Complexity Theory, bringing together techniques from the Permanent versus Determinant problem, the Complexity Zoo, and structural results about symmetric group and general linear group representations. It aims to translate computational lower bounds into explicit geometric and representation-theoretic certificates, connecting to longstanding problems in mathematics and theoretical computer science.
Background and motivation
The program originates in attempts to resolve the Permanent versus Determinant problem and to situate the P versus NP problem within algebraic and geometric frameworks, drawing on historical influences from the Hilbert's problems, the Grothendieck school, and the development of complexity theory at institutions like Princeton University and Institute for Advanced Study. Founders cited motivations from earlier work by Valiant, Mulmuley, and Sohoni themselves, and from connections to the Geometric Langlands program, the Riemann–Roch theorem, and the study of orbit closures under group actions such as those of the general linear group and the symmetric group. The program leverages structural results like the Schur–Weyl duality, the Littlewood–Richardson rule, and the Peter–Weyl theorem to formulate complexity separations as questions about occurrence obstructions and multiplicity obstructions.
Formal statement of the program
At its core the program proposes that separating complexity classes reduces to showing non-containment of particular orbit closures or varieties: for example, demonstrating that the orbit closure of the permanent polynomial is not contained in the orbit closure of the determinant polynomial for suitable sizes, an approach that reframes computational hardness as a geometric inclusion problem influenced by the Nullstellensatz and the Hilbert–Mumford criterion. The formalism uses representations of groups such as the GL_n family and modules characterized by Young diagrams and highest weights, invoking tools like the Kronecker coefficients, the plethysm problem, and multiplicity formulas from Weyl character theory. The program asserts that explicit, stable obstructions arising from representation theory—for instance, vanishing of specific Littlewood–Richardson coefficients or nonvanishing of certain Kronecker coefficients—would yield proofs of complexity separations conjectured in the Complexity Zoo.
Geometric complexity theory framework
Geometric Complexity Theory (GCT) frames complexity questions as problems about algebraic varieties and coordinate rings with actions by classical groups such as GL_n and the symmetric group. It studies the orbit closures of polynomials like the determinant and the permanent under group actions, employing invariants from invariant theory, the Hilbert scheme, and the theory of GIT quotients developed by David Mumford and contemporaries. The framework uses the language of coordinate rings, decomposition into irreducible GL_n-modules, and detection of obstructions through multiplicity comparisons involving objects like Schur functions, Weyl modules, and Young tableaux. GCT connects to computational models such as algebraic circuits, arithmetic circuits, and classes including VP and VNP formalized by Valiant.
Major results and progress
Progress includes structural results on multiplicities, asymptotic positivity theorems, and relations between Kronecker and plethysm coefficients, with contributions from researchers at institutions like Carnegie Mellon University, University of Chicago, and Microsoft Research. Notable milestones include conditional reductions of certain lower bounds to existence of obstructions, development of algorithms for estimating multiplicities using semigroup methods and connections to Einstein–Weyl geometry in specific settings, and results clarifying limits of occurrence-obstruction approaches following critiques by papers from groups led by researchers such as Bürgisser, Ikenmeyer, and Panova. Work on explicit constructions of highest-weight vectors, combinatorial models for Kronecker coefficients, and plethysm bounds in special cases has advanced knowledge about which representation-theoretic pathways might yield obstructions.
Techniques and conjectures
Techniques used encompass algebraic geometry constructions like desingularization, the use of Young diagrams and tableaux combinatorics for representation multiplicities, and computational approaches leveraging linear programming, semidefinite programming, and algorithmic aspects of Geometric Invariant Theory. Conjectures central to the program include forms of the occurrence obstruction conjecture, predictions about positivity and saturation of Kronecker coefficients, and expected relationships between orbit closure containment and complexity class separations such as VP versus VNP. The program proposes explicit candidates for obstructions drawn from combinatorial representation data and formulates hypotheses about log-concavity, asymptotic behavior tied to Ehrhart polynomials, and stability phenomena analogous to those in the representation stability literature.
Criticisms and open problems
Critiques have targeted the viability of occurrence obstructions after negative results showing limits on separating power in many regimes, with influential counterexamples and limitations published by teams including Ikenmeyer, Mulmuley, and Bürgisser. Open problems include constructing explicit superpolynomial obstructions that withstand known barrier results, clarifying the role of multiplicity versus occurrence obstructions, resolving conjectures about Kronecker coefficient positivity, and determining whether refinements of GCT can circumvent current lower-bound barriers identified by researchers at ETH Zurich, Princeton University, and University of Toronto. Further work seeks to integrate ideas from the Geometric Langlands program, the theory of categorification, and advances in computational algebra from groups at MIT and Harvard University to strengthen or redirect the program’s approach.