Mulmuley–Sohoni multiplicity conjecture for geometric complexity theory
The complexity classes and are considered through representation-theoretic multiplicities associated with them. Mulmuley–Sohoni multiplicity conjecture. There exist representation-theoretic multiplicities that are zero for and nonzero for . The conjecture was formally stronger than the condition needed for the preceding implication from a multiplicity separation to .
References
Status
- Refuted: Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory (Journal of the American Mathematical Society, 2019) https://www.ams.org/journals/jams/2019-32-01/S0894-0347-2018-00908-7/
Source: Joshua A. Grochow, “NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications”, arXiv:1610.05825 (2016).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.