Mulmuley–Sohoni multiplicity conjecture for geometric complexity theory
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 . The supplied status evidence says that this conjecture was recently disproved.
Sources & referencesView supporting material
Primary 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.