Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
复制标题
几何复杂性理论 II：针对类别变体之间嵌入的显式障碍
DOI：
10.1137/080718115
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Sohoni
中科院分区：
文献类型：
--
作者：
K. Mulmuley;M. Sohoni
在[K.D.MulMuley和M.Sohoni，SIAM J.Comput，31(2001)，pp.496-526]中，我们提出了一种通过几何不变量理论来研究复杂性理论中$P$与$NP$以及相关下界问题的方法。特别地，它将$NP\NOT\SUBSEQ P$猜想的算术(特征为零)版本归结为证明与复杂性类$NP$相关的簇不能嵌入与复杂性类$P$相关的簇的问题。我们称这些与复杂性类有关的类簇为$P$和$NP$。本文进一步发展了这一方法，将这些下界问题--它们都是不存在的问题--归结为一些存在问题：具体地说，证明了在类簇之间存在对这种嵌入的障碍。对于这种障碍的显式构造，它给出了两个结果。第一个结果是将Borel-Weil定理推广到一类包含类簇的轨道闭包。第二个结果是与复杂性类$NC$有关的类簇的不变理论第二基本定理的猜想类似的较弱形式。这些结果表明，复杂性理论中的基本下界问题反过来又与代数几何和表示论中的显式构造问题密切相关。这里的结果是在[K.D.MulMuley和M.Sohoni，《代数和几何进展》(海得拉巴，2001美元)中宣布的，印度斯坦书局，印度新德里，2003年，第239-261页]。
In [K. D. Mulmuley and M. Sohoni, SIAM J. Comput., 31 (2001), pp. 496-526], henceforth referred to as Part I, we suggested an approach to the $P$ vs. $NP$ and related lower bound problems in complexity theory through geometric invariant theory. In particular, it reduces the arithmetic (characteristic zero) version of the $NP \not \subseteq P$ conjecture to the problem of showing that a variety associated with the complexity class $NP$ cannot be embedded in a variety associated with the complexity class $P$. We shall call these class varieties associated with the complexity classes $P$ and $NP$. This paper develops this approach further, reducing these lower bound problems—which are all nonexistence problems—to some existence problems: specifically to proving the existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel-Weil theorem to a class of orbit closures, which include class varieties. The second result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class $NC$. These results indicate that the fundamental lower bound problems in complexity theory are, in turn, intimately linked with explicit construction problems in algebraic geometry and representation theory. The results here were announced in [K. D. Mulmuley and M. Sohoni, in Advances in Algebra and Geometry (Hyderabad, $2001$), Hindustan Book Agency, New Delhi, India, 2003, pp. 239-261].