Categorical complexity

DOI10.1017/FMS.2020.26MaRDI QIDQ3304647zbMATH OpenOpenAlexFDO

Authors Saugata Basu, Umut Isik

Publication date 3 August 2020

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1610.07737

zbMATH Keywords

algebraic geometryarithmetic circuitcategory theorycomplexity theorygraph theory

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Graphs, diagram schemes, precategories (18A10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: 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, semi-linear and semi-algebraic 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 non-uniform computational complexity (such as circuit complexity), while on the other hand it has features which 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.

Recommendations

• From objects to diagrams for ranges of functors
• Kolmogorov complexity of categories
• Timed Sets, Functional Complexity, and Computability
• scientific article; zbMATH DE number 2125663
• A categorical view to structural complexity

Cites work

• A complexity theory of constructible functions and sheaves
• Algebraic geometry II
• Algorithms in real algebraic geometry
• An introduction to category theory
• Betti number bounds, applications and algorithms
• Completeness and reduction in algebraic complexity theory
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity classes and completeness in algebraic geometry
• Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem
• Descriptive complexity: a logician's approach to computation.
• Effective Hironaka resolution and its complexity
• Feasible arithmetic computations: Valiant's hypothesis
• Geometric Invariant Theory
• Greatest common divisors of polynomials given by straight-line programs
• scientific article; zbMATH DE number 5761737 (Why is no real title available?)
• scientific article; zbMATH DE number 193320 (Why is no real title available?)
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1515218 (Why is no real title available?)
• scientific article; zbMATH DE number 1840601 (Why is no real title available?)
• scientific article; zbMATH DE number 3223483 (Why is no real title available?)
• Sheaves in geometry and logic: a first introduction to topos theory
• The complexity of computing the permanent
• Ubiquity of Łojasiewicz's example of a nonbasic semialgebraic set

Cited in

(7)

• A categorical view to structural complexity
• Category and Measure in Complexity Classes
• Decomposing the complexity quotient category
• Kolmogorov complexity of categories
• From objects to diagrams for ranges of functors
• Computing the homology functor on semi-algebraic maps and diagrams
• Preserving categoricity and complexity of relations

This page was built for publication: Categorical complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304647)