[Computational complexity and category theory] seem like such natural pairs.
Given the prominence of computational complexity as a research field, if they were such natural bedfellows, maybe somebody would have brought out the
Let me entertain the reader with thoughts about why a categorical rendering of computational complexity is hard. Arguably, the
key concept cluster in category theory is centering around universal
constructions / properties (with the associated apparatus of functors,
natural transformations, adjunctions and so on). If we can show that a
mathematical construction has a universal property, that gives a lot
So if we wanted a categorical approach to computational complexity, we'd
need to find a convenient category and exhibit how key concepts of complexity theory (e.g. LOGSPACE
or NP-hardness) can be given by universal constructions using that category. This has not
yet been done, and I think that this is because it's a really difficult problem.
I suspect that the reason for this difficulty is that the key object of
complexity theory, the Turing machine, is not well understood algebraically. The
problem with TMs is that they are not naturally equipped with a nice
algebra that allows building up programs in a compositional way. By
that I mean that we don't usually program TMs by saying our target
program is the TM T which is composed as e.g. $T = T_1 \oplus T_2
\otimes T_3$ where the $T_i$ are 'smaller' TMs and $\oplus, \otimes$ are
algebraic operators on TMs: we just don't have (natural) algebraic operations on TMs that
enable us to build up TMs in stages in an insightful way1. Instead, we construct TMs by specifying their two
components separately: the control (a FSM) and the tape.
Neither control nor tape have good algebras
Let's look at tapes first. There are a couple of natural
ways to compose tapes, none of which appear to work for a compositional
description of TMs.
Glue them together like ordinal addition.
This isn't the right notion, because tapes are infinite and by
sticking them together like ordinal addition we obtain a double
infinite object that goes beyond finite computability, leading to
infinite computation / hypercomputation, which are interesting as
mathematical but don't correspond to feasible computation.
Stick them in parallel, e.g. two 3-head machines turn into a 6-head
machine. This doesn't tell us how the component machines interact
with each other.
Interleave tapes. One problem with this approach is that it's
unclear what the canonical interleaving might be, if any. Moreover,
interleaving will 'confuse' existing control, which tends to be
finely tuned towards a specific tape layout. So we can't reuse control directly.
With FSMs the situation is a bit better, because we do have computationally meaningful algebraic
theories of automata construction, the most well-know of which might
be process algebras like CSP, CCS, $\pi$-calculus, ACP and so on. But
none of them is a calculus of tape-head movements, which is what we'd
need if we wanted to compose TMs.
All in all, we are quite far away form a substantial algebraic /
categorical treatment of computational complexity, and we'd need
several conceptual advances to get there.
1 Note that this is
quite different from other computational formalisms like
$\lambda$-calculus and $\pi$-calculus, which are algebraic
calculi. Because they are algebraic, it has been easy to develop
type-theories for $\lambda$-calculus and $\pi$-calculus as a way to
constrain programs. However these calculi have powerful operations like
new-name generation, scope extrusion, $\alpha$-conversion and unlimited copying of terms, which
make them a priori unsuitable as basic formalisms for complexity theory. Indeed one can easily show e.g. P = NP if one isn't careful. It was only in 2014 that Accattoli and Dal Lago showed (in: Beta Reduction is Invariant, Indeed) that $\lambda$-calculus can be used for defining time-complexity if one is careful. No corresponding results are known for space complexity, or for $\pi$-calculus.