Mulmuley–Sohoni's strengthened permanent versus determinant conjecture

About 14 years old · traced to

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

Detm=GL⁡(V)⋅det⁡m‾,Permnm=GL⁡(V)⋅xm,mm−nperm⁡n‾.\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.

References

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.