Mulmuley–Sohoni multiplicity conjecture for geometric complexity theory

The complexity classes VPws{\mathsf{VP}}_{ws} and VNP{\mathsf{VNP}} are considered through representation-theoretic multiplicities associated with them. Mulmuley–Sohoni multiplicity conjecture. There exist representation-theoretic multiplicities that are zero for VPws{\mathsf{VP}}_{ws} and nonzero for VNP{\mathsf{VNP}}. The conjecture was formally stronger than the condition needed for the preceding implication from a multiplicity separation to VPwsVNP{\mathsf{VP}}_{ws}\neq{\mathsf{VNP}}. 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

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.