Geodesic
CATEGORICAL COMPLEXITY
Forum of Mathematics, Sigma, Tome 8 (2020)

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
@article{10_1017_fms_2020_26,
     author = {SAUGATA BASU and UMUT ISIK},
     title = {CATEGORICAL {COMPLEXITY}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {8},
     year = {2020},
     doi = {10.1017/fms.2020.26},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2020.26/}
}
TY  - JOUR
AU  - SAUGATA BASU
AU  - UMUT ISIK
TI  - CATEGORICAL COMPLEXITY
JO  - Forum of Mathematics, Sigma
PY  - 2020
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2020.26/
DO  - 10.1017/fms.2020.26
LA  - en
ID  - 10_1017_fms_2020_26
ER  - 
%0 Journal Article
%A SAUGATA BASU
%A UMUT ISIK
%T CATEGORICAL COMPLEXITY
%J Forum of Mathematics, Sigma
%D 2020
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2020.26/
%R 10.1017/fms.2020.26
%G en
%F 10_1017_fms_2020_26
SAUGATA BASU; UMUT ISIK. CATEGORICAL COMPLEXITY. Forum of Mathematics, Sigma, Tome 8 (2020). doi: 10.1017/fms.2020.26

Cité par Sources :