Introduction and motivation
Computational complexity is a mathematical topic that is studied by theoretical computer scientists with mathematical rigor. A central problem of the area is the famous vs
problem. However, (from personal experience) a typical run-of-the-mill “working mathematician” (say working in algebraic geometry or pde’s) often has a somewhat hazy picture of what the field is about. Sure, sometimes a statement such as “such or such problem admits an efficient algorithm or is NP-hard” occurs as a “remark” in a couple of their papers — but often such “remarks” are carefully separated from the “proper mathematics” in the paper. There are some good reasons for this state of affairs — and I allude to them later.
The motivation behind this post is two-fold:
- To convince “the working mathematician” or perhaps “the working category theorist” that “complexity” (removed from the standard paradigm of Turing machines and “membership problems in languages”) can be an interesting notion worth their attention.
-
To argue that it is possible to define complexity of mathematical objects in a natural (categorical) way (think what is the “complexity” of your favorite variety or scheme or manifold or even a morphism between objects of these categories ?) — and the manner in which such “complexity” transforms under your favorite functors bear some relationship (by analogy) with the classical questions such as
vs
. Such functor complexity can also be interesting in its own right — and indeed has been studied extensively in particular cases, (even in my own little corner of math, namely real algebraic geometry) though not using the categorical language.
Standard disclaimers:
In what follows I assume no knowledge of complexity theory, but assume basic familiarity with some standard notions from category theory.
It goes without saying that the views expressed are mine and may not reflect those of my co-authors/co-conspirators.
(Classical) Complexity theory in a nutshell : P, NP, PH and all that
Computational complexity studies complexity of languages. In its original avatar, a language is a set of
strings — that is
is a subset of
. (This emphasis on
or “bits” has to do obviously with digital computers — and we will escape from this tyranny of bits and machines at the first opportunity.) But staying within the “bit framework” for the moment — one says that the complexity of a language
is bounded by a function
if there exists a Turing machine
, such that for every
the number of steps
takes to decide if an element
belongs to
is bounded by
. The language
belongs to the class
if and only if the function
can be taken to be a polynomial.
The definition of the class is quite robust. For instance, the precise details of the definition of “Turing machine” is not very important. One can replace the notion of a Turing machine by any reasonable programming language without changing the definition of the class
. There is also a “non-uniform” version of the class
(which is (provably) not equal to the class
described before) using circuits (rather than Turing machines) — the non-uniformity referring to the fact that the circuits for different
are independent of each other. (Warning. The word “circuit” here does not refer to the minimally dependent sets in a matroid, but rather to ones found in digital computers — with “gates” encoding logical connectives and “wires” feeding into and out of such gates).
Let us denote the subset by
. One says that a language
belongs to the class
, if and only if there exists a language
belonging to the class
, and a polynomial
, such that
, where
denotes the projection on the last
factors. Thus, each language in
is an image under projection (strictly speaking a sequence of projections) of languages in
. Equivalently, they can be described using one block (of size typically growing with
) of existential quantifiers applied to a language in
— eliminating a block of existential quantifiers is expressing in the language of logic, the geometric act of taking image under projection along certain variables. The “
” in
has to do with “non-deterministic” Turing machines —
is more intuitive (but not standard !). Replacing
by the
one obtains the class traditionally called
(one should perhaps call it
). Indeed by alternating the existential and the universal quantifiers, one obtains an hierarchy of complexity classes (in the same spirit as the arithmetic hierarchy of Kleene in logic) called the polynomial hierarchy (denoted
— no quibble with nomenclature here). It is unknown whether this is a proper hierarchy or it collapses down to
(or to some other finite level).
But I promised that we will escape the tyranny of “bits” and “machines” — which we do now (one morsel at a time) starting with bits first.
Escaping the tyranny of “bits” (Blum-Shub-Smale, Poizat)
In order to “model” continuous computations (for example, those arising in numerical analysis) Blum, Shub and Smale (1989) defined rigorously a notion of a computing machine that took as input real numbers (also complex numbers). In fact, what they defined is a machine capable of accepting inputs which are tuples of finite lengths with entries from a real closed field or an algebraically closed field
. Letting
denoting either
or
, in analogy with the classical case the language accepted by a Blum-Shub-Smale (henceforth B-S-S) machine over
, is a subset of
.
The, definition of when such a language is in the class
(subscript
denoting the field) is now the same as in the classical case. If
belongs to the class
, then there is a B-S-S machine accepting
with polynomially bounded steps (and so in particular such a machine terminates in finitely many steps on every possible input). This last observation implies that (the
-th part),
, of
is a semi-algebraic subset of
if
, or a constructible subset of
if
.
Blum-Shub-Smale went further. Once we have the class , the definitions of
, are now automatic (using existential/universal quantifiers as in the classical case). Blum-Shub-Smale proved the existence of
problems etc. In a similar spirit, but from a more model-theoretic point of view, Bruno Poizat generalized Blum-Shub-Smale results to more general structures (B. Poizat, Les petits cailloux. Une approche modèle-théorique de l’algorithmie. 1995).
The Blum-Shub-Smale version of the vs
for
begins to resemble problems more familiar to run-of-the-mill mathematicians — because they boil down to the question whether the images under projections of “easy” semi-algebraic/constructible subsets remain “easy” — or are provably “hard”. Here “easy/hard” refers to belonging/not belonging to the class
. Over the reals, one would prove
, if one could show that the sequence of real quartic polynomials in
variables (i.e the tuples of their coefficient vectors) admitting a real solution is not in
. Not that it has helped till date, but certainly thinking about discriminant varieties over real closed or algebraically closed fields — these varieties appear naturally when considering systems of polynomial equations having common zeros — are easier than thinking of images of projections of subsets of the Boolean hypercube.
Escaping the tyranny of “machines” (diagram computations)
But a certain annoyance remains. Firstly, as we are taught in (abstract) linear algebra, one should not really think of polynomials (for example the quartic polynomials of the last paragraph) as a tuple of coefficients — because this amounts to choosing arbitrarily a basis for the vector space of polynomials. Rather, a “polynomial in variables”, is an element of
where
is an
-dimensional vector space. The discriminant varieties that arise have geometric descriptions — which do not require fixing any bases. Wouldn’t it be nice to have a basis-free definition of “complexity” as well ?
And then there is still the role played by “machines/circuits” in the definition of the all important class . All these models fit into the mould of “input/output framework” — which seem to force choice of a basis.
Categorical complexity
We (Umut Isik and I) propose an alternative in this paper. We delink complexity from membership questions, and take a categorical viewpoint — and aim at defining a notion of “complexity” — not just of objects, or arrows, but of arbitrary finite diagrams in any given category. Here is the basic idea. To see the details one needs to look at the paper. Fix a category (for example, the category of
-vector spaces), and a set of morphisms
of
which we call the set of basic morphisms (in the case of
-vector spaces, we take
to be the set of homotheties
, the zero morphisms
, along with the morphism
). Each morphism in
is given unit cost. We now define a way of assigning cost to arbitrary (finite) diagrams.
A natural way in any category to build more complicated objects and morphisms from simpler ones in categories is to take limits or colimits of diagrams. This motivates our definition of what we call diagram computation in our paper. At each step of such a “computation” one is allowed to take a limit or colimit of a sub-diagram of the existing diagram (if it exists in the category ) and thus obtain a larger diagram. The categorical complexity then of an arbitrary diagram is the minimum number of such steps required + the size of the initial diagram, to produce a diagram in which a copy of the given diagram occurs as a subdiagram. While the choice of the initial set of basic morphism might be seen as arbitrary, there are no other choices involved — and limits/colimits being only defined up to isomorphisms — isomorphic diagrams/objects/morphisms automatically have identical complexity. Restricting diagram computations to those which only use limits (resp. colimits), we have a notion of (categorical) limit (resp. colimit) complexity as well.
Just to stay grounded, here is an example (which appears in our paper) of a diagram computation in the category -vector space using only limits which computes the morphism
. The cone of the final limit is displayed using a red curve. This last limit is isomorphic to
and one of the arrows out of the limit is the morphism we wanted to compute.
This way of defining “complexity” might seem outlandish at first glance — and might seem to be very far removed from the usual machine-driven definitions of complexity — but we show that in certain standard categories — for example, category of affine -schemes, the categorical complexity of say an affine sub-variety
is closely related to the “circuit complexity” of the polynomials cutting out
. So the notion is not as outlandish as it might seem at first glance.
Complexity of functors
Once we have a well-defined notion of complexity for (diagrams in) categories, we can define complexity of functors. Given a functor , between two categories (each with its own set of basic morphisms), we define the complexity of the functor
to be the function,
to the supremum over all diagrams
in
of complexity bounded by
, the complexity in the category
of
.
We will see below how functor complexity impinges on several aspects of categorical theory — for instance categorical analogs of vs
. However, complexity of functors arise (informally) in may different guises — often when one proves “quantitative bounds”.
For example, in applications of real algebraic geometry an important role played is played by results bounding the Betti numbers of real semi-algebraic sets in terms of the size of the formula defining the set (often measured by the sum of the degrees of the polynomials appearing in the formula). The first results in this direction was proved by Oleĭnik and Petrovskiĭ (On the topology of real algebraic surfaces. (Russian) Doklady Akad. Nauk SSSR (N.S.) 67, (1949) 31–32), and later generalized in various ways (for example, see here). These bounds are not in the framework of categorical complexity.
However, if one fixes a notion of categorical complexity for the category of semi-algebraic sets, and also for
-modules — then one can formally ask for the complexity of the homology functor
. The known results on upper bound on the Betti numbers of semi-algebraic sets in terms of the number and degrees of the defining polynomials do not immediately produce an upper bound on the functor complexity of
. Thus, to obtain a tight upper bound on this functor complexity is an open problem.
Role of adjoint functors
Category theory will not be so interesting without the notion of adjoint functors — so it is not surprising that they should play a role in categorical complexity as well. For one thing, one knows that right adjoints preserve limits and left ones preserve colimits. As a result, right adjoint functors will preserve (upper bounds on) limit and left adjoints preserve (upper bounds on) colimit complexity (assuming that the functor takes basic morphisms to basic morphisms). But the role of adjoints is even visible at the level of classical complexity. Recall that classes were related to the class
through a projection map
(we are being loose here and forgetting about the fact that we are talking about sequences of sets and not just one set). Let
be sets and
(you can think of
,
the projection to the last
factors. Now the map
induces three maps
The first and the second one are the direct image and the inverse image maps induced by , while the third map
is defined by
. Thinking of
and
as poset categories (partial order corresponding to inclusion), the maps
correspond to functors, and
is left adjoint to
which is left adjoint to
(Exercise!).
The connection with complexity is this. It is easy to prove that unlike taking direct image, the pull-back under a projection of an “easy” language is again “easy”. Thus, the complexity class is preserved under pull-backs of projections. In other words given an “easy” set
,
is again “easy”. But the question of whether given an “easy” set
, whether
is again easy, is related to the
and
respectively.
In category theory, functors often come in adjoint pairs (and often one of the pair is more interesting than the other). The same thing seems to happen in the world of complexity of functors — often in an adjoint pair one functor has polynomially bounded complexity, while the other does not (conjecturally). More here.
Complexity of the image functor
A particular case of functor complexity (where adjointness also plays a role) is of particular interest. Let be a category and let
denote the diagram category corresponding to the diagram
. Its objects are morphisms in the category
. Let
denote the subcategory of
which are monomorphism, and let
denote the inclusion functor. One says that the category
has images if the the functor
has an adjoint (which if it exists we denote by
). For example, the category of sets, groups, or the category
of semi-algebraic sets and maps, have images. This is because for every morphism
in these categories, there exists a monomorphism
(for the category
this fact is a consequence of the Tarski-Seidenberg theorem which guarantees that the image of a semi-algebraic map is semi-algebraic).
If one has a category having images, then starting from the definition of complexity in the category one obtains naturally a definition of complexity in the categories
and
. This in turn determines the complexity of the functor
. The functor complexity of
is a function — and it is meaningful to ask if this function is polynomially bounded. Remember our discussion about
and
in various settings. We saw that question whether
is fundamentally about the extent to which complexity of an object increases under taking the images of the object under certain maps. This blow-up in complexity in the world of categorical complexity is measured by the complexity of the image functor (if it exists). It is thus natural to posit that the question of whether the complexity of the image functor in a category
is polynomially bounded or not is the categorical analog of
.
Postscript and Quo Vadis
Our motivation in developing categorical complexity has to do more in developing a proper framework to study “complexity” of mathematical objects and functors — rather than using it as a tool for proving actual lower bounds interesting to computer scientists (even though I will not be unhappy if categorical insights contribute to that goal). Also there is some parallel work. For instance, Noson Yanofsky develops a somewhat similar notion of computation using Kan extensions (of which limits and colimits are special cases). But his goals seem to be different from ours — as we want to stay closer to everyday mathematics and functor complexity does not seem to as central in his work as in ours. There are many questions that we list on the paper. We hope to answer some of them in the future, but I will be happier if it attracts the attention of category theorists to complexity theory seen from a categorical point of view.
Finally, one anonymous referee asked : “Can lower bound techniques like diagonalization, relativization, and natural proofs be carried over to categorical complexity ? ” I have nothing to say about this at this point — but food for future thought.