Is there a theory that combines category theory/abstract algebra and computational complexity? Category theory and abstract algebra deal with the way functions can be combined with other functions.  Complexity theory deals with how hard a function is to compute.  It's weird to me that I haven't seen anyone combine these fields of study, since they seem like such natural pairs.  Has anyone done this before?



As a motivating example, let's take a look at monoids.  It's well known that if an operation is a monoid, then we can parallelize the operation.

For example in Haskell, we can trivially define that addition is a monoid over the integers like this:

instance Monoid Int where
    mempty = 0
    mappend = (+)


Now if we want to compute the sum of 0 to 999, we could do it sequentially like:

foldl1' (+) [0..999]


or we could do it in parallel

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel


But parallelizing this monoid makes sense only because mappend runs in constant time.  What if this weren't the case?  Lists, for example, are monoids where mappend does not run inconstant time (or space!).  I'm guessing this is why there is no default parallel mconcat function in Haskell.  The best implementation depends on the complexity of the monoid.



It seems like there should be a convenient way to describe the differences between these two monoids.  We should then be able to annotate our code with these differences and have programs automatically choose the best algorithms to use depending on a monoid's complexity.
[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
connection already?

Wild speculation.
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
of insight.
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
themselves. 

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.