Complexity Classes and Completeness in Algebraic Geometry
Complexity Classes and Completeness in Algebraic Geometry
复制标题
代数几何的复杂性类别和完备性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Umut Isik
中科院分区：
文献类型：
--
作者：
M. Umut Isik
研究了射影簇序列的计算复杂性。我们定义类似的复杂性类P和NP这些和证明NP-完备性的序列称为通用电路结果。这是第一个家庭的紧凑空间被证明是NP完全的几何设置。
We study the computational complexity of sequences of projective varieties. We define analogues of the complexity classes P and NP for these and prove the NP-completeness of a sequence called the universal circuit resultant. This is the first family of compact spaces shown to be NP-complete in a geometric setting.