Mulmuley–Sohoni's strengthened permanent versus determinant conjecture

Let V=Cm2V=\mathbb{C}^{m^2}, let detm\operatorname{det}_m be the determinant polynomial on m×mm\times m matrices, and let permn\operatorname{perm}_n be the permanent of the upper-left n×nn\times n submatrix. Define the orbit closures

Detm=GL(V)detm,Permnm=GL(V)xm,mmnpermn.\mathcal{D}et_m=\overline{\operatorname{GL}(V)\cdot\operatorname{det}_m},\qquad \mathcal{P}erm_n^m=\overline{\operatorname{GL}(V)\cdot x_{m,m}^{m-n}\operatorname{perm}_n}.

Mulmuley–Sohoni's strengthened conjecture. For each c>0c>0 and infinitely many nn, Permnnc⊈Detnc\mathcal{P}erm_n^{n^c}\not\subseteq\mathcal{D}et_{n^c}. This is a central geometric-complexity-theoretic formulation of the difficulty of representing the permanent by determinants; its resolution remains open.

Sources & referencesView supporting material

Primary source

Joshua A. Grochow and Korben Rusek, “Report on "Mathematical Aspects of P vs. NP and its Variants."”, arXiv:1203.2888 (2012).

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.