CATEGORICAL COMPLEXITY
CATEGORICAL COMPLEXITY
复制标题
范畴复杂性
DOI：
10.1017/fms.2020.26
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
ISIK, UMUT
中科院分区：
文献类型：
--
作者：
BASU, SAUGATA;ISIK, UMUT
我们介绍了一个概念的复杂性图（特别是，对象和态射）在任意类别，以及一个概念的复杂性函子之间的类别配备了复杂性功能。我们讨论了几个例子，这个新的定义在广泛的共同利益，如有限集，布尔函数，拓扑空间，向量空间，半线性和半代数集，分级代数，仿射和投影品种和计划，以及模块在多项式环。我们表明，一方面，分类复杂性恢复在几个设置的经典概念的非均匀的计算复杂性（如电路复杂性），而另一方面，它的功能，使它在数学上更自然。我们还假设，研究函子复杂性是复杂性理论中关于分离不同复杂性类的经典问题的范畴模拟。
We introduce a notion of complexity of diagrams (and, in particular, of objects and morphisms) in an arbitrary category, as well as a notion of complexity of functors between categories equipped with complexity functions. We discuss several examples of this new definition in categories of wide common interest such as finite sets, Boolean functions, topological spaces, vector spaces, semilinear and semialgebraic sets, graded algebras, affine and projective varieties and schemes, and modules over polynomial rings. We show that on one hand categorical complexity recovers in several settings classical notions of nonuniform computational complexity (such as circuit complexity), while on the other hand it has features that make it mathematically more natural. We also postulate that studying functor complexity is the categorical analog of classical questions in complexity theory about separating different complexity classes.
登录
查看更多内容
可构造函数和滑轮的复杂性理论
影响因子：
3
作者：
S. Basu
通讯作者：
S. Basu
Betti 数界、应用和算法
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
S. Basu;R. Pollack;Marie
通讯作者：
Marie
代数几何的复杂性类别和完备性
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
M. Umut Isik
通讯作者：
M. Umut Isik
连接的连通性、上同调量词消除和代数 Toda 定理
DOI：
10.1007/s00029-020-00596-0
发表时间：
2020
期刊：
Selecta Mathematica
影响因子：
--
作者：
Basu, Saugata;Patel, Deepam
通讯作者：
Patel, Deepam
DOI：
--
发表时间：
1988
期刊：
JACM
影响因子：
--
作者：
E. Kaltofen
通讯作者：
E. Kaltofen