Is there a theory that combines category theory/abstract algebra and computational complexity?

Question

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.

Answer 1

[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 way¹. 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.

---

¹ 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.

Answer 2

This answer about isomorphisms between formal languages combines algebraic results from the theory of codes with notions from category theory to investigate possible notions of equivalence and isomorphism between formal languages and complexity classes.

My own interpretation of these results is that synchronization points in words are different for deterministic and unambiguous non-deterministic transducers, and even different between deterministic forward and deterministic backward transducers. Taking this perspective of synchronization points allows to connect these results to visibly pushdown languages, and raises the question whether those should also consider simple separators (like a space or a comma) in addition to calls and returns. (My guess is that a separator could be emulated by a combined return+call, but because those require two symbols instead of one, it's not clear to me whether this is sufficient. There might also be visibly languages which have only separators, but no call or return symbols.)