<blockquote>
  <p>[Computational complexity and category theory] seem like such natural pairs.</p>
</blockquote>

<p>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?</p>

<p><strong>Wild speculation.</strong>
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.</p>

<p>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<sup>1</sup>.  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. </p>

<p>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.</p>

<ul>
<li><p><strong>Glue them together like ordinal addition.</strong>
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.</p></li>
<li><p><strong>Stick them in parallel</strong>, 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.</p></li>
<li><p><strong>Interleave tapes.</strong> 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.</p></li>
</ul>

<p>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.</p>

<p>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.</p>

<hr>

<p><sup>1</sup> 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: <a href="http://arxiv.org/abs/1405.3311">Beta Reduction is Invariant, Indeed</a>) 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.</p>

CC BY-SA 4.0
2018-07-30T12:13:57.360Z
I'd say that the composition of Turing machines is fairly clear when you think about them as abstract computer programs. The natural way to compose programs is to call one as a subprogram of another. More generally, each program is a computable in finite time and space function which accepts certain formatted input and outputs another formatted string, which can be fed into another function. It's possible that some garbage inputs will result in garbage outputs or that some function fails to execute in the allotted time and space, in which case the whole program crashes.
Anton Fetisov
CC BY-SA 4.0
2018-07-30T12:14:09.217Z
Obviously no all programs are composable in this way, which naturally leads us to a category of TMs. It's also likely that one should let go the notion of a time-space unlimited TM, which isn't practically feasible anyway. Is there some published notion which captures this structure?
Anton Fetisov
CC BY-SA 4.0
2018-07-30T23:42:29.127Z
@AntonFetisov Have you tried writing down the details? It's not pretty.
Martin Berger
CC BY-SA 4.0
2022-06-21T16:20:50.550Z
@AntonFetisov this idea of calling subprograms – ignoring any notion of inputs being of a „correct“ or „incorrect type“ – might fit into the framework of [operads](https://en.wikipedia.org/wiki/Operad).
Lukas Juhrich
CC BY-SA 3.0
2015-07-22T12:08:44.227Z
2015-07-22T12:08:44.227Z
Martin Berger
<p>This <a href="https://cs.stackexchange.com/questions/24574/what-are-appropriate-isomorphisms-between-formal-languages/43564#43564">answer</a> 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.</p>

<p>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.)</p>

CC BY-SA 3.0
2015-07-21T07:36:13.733Z
I made this a community wiki, because it links to my own answer to my own question, which is certainly not great. I was "cleaning" my favorites, and just writing this short answer was the easiest way to proceed.
Thomas Klimpel
CC BY-SA 3.0
2015-07-21T07:29:04.217Z
2015-07-21T07:47:56.557Z
2017-04-13T12:48:30.830Z
Thomas Klimpel
<p>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?</p>

<hr>

<p>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.</p>

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

<pre><code>instance Monoid Int where
    mempty = 0
    mappend = (+)
</code></pre>

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

<pre><code>foldl1' (+) [0..999]
</code></pre>

<p>or we could do it in parallel</p>

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

<p>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.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2012-08-03T17:44:39.470Z
Type Integer in Haskell is multi-precision integers, and the time complexity of addition on them naturally depends on the length of the input integers, so it is misleading to say that mappend in your Monoid instance for Integer runs in constant time.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-03T18:01:59.807Z
@TsuyoshiIto  You're right, I meant to use Int.  Fixed.
Mike Izbicki
CC BY-SA 3.0
2012-08-03T21:51:25.097Z
Have you seen [this question](http://cstheory.stackexchange.com/questions/3074/a-category-of-np-complete-problems)?
Kaveh
CC BY-SA 3.0
2012-08-04T00:06:50.210Z
@Kaveh I hadn't, thanks for the pointer.  From a quick read through it sounds like no one's done any category theoretic work on complexity classes themselves (and there's some debate about what that might even mean or if it's a worthwhile goal).  So I think that pretty much answers the first part of my question and just leaves any interactions between algebra and complexity.
Mike Izbicki
CC BY-SA 3.0
2012-08-04T00:08:25.583Z
The are a lot of interaction between algebra and complexity theory. There are even books titled "Algebraic Complexity Theory" which use and apply algebraic concepts and techniques to complexity. And there are also extensive works applying complexity theory to algebra. You have to be more specific to get an answer.
Kaveh
CC BY-SA 3.0
2012-08-04T00:30:40.140Z
Btw, it appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).
Kaveh
CC BY-SA 3.0
2012-08-04T00:31:05.773Z
http://math.stackexchange.com/q/178207/
Kaveh
CC BY-SA 3.0
2012-08-04T02:59:46.687Z
@Kaveh Okay, I think I get the rules now.
Mike Izbicki
CC BY-SA 3.0
2012-08-07T20:50:48.783Z
How about homology of some sort?
Joshua Herman
CC BY-SA 3.0
2015-07-22T12:14:57.750Z
@Kaveh Isn't the book "Algebraic Complexity Theory"  mostly about the computational complexity of algebraic operations like multiplication of polynomials?
Martin Berger
<cc.complexity-theory><algebra><algebraic-complexity>
Is there a theory that combines category theory/abstract algebra and computational complexity?
Mike Izbicki
# Is there a theory that combines category theory/abstract algebra and computational complexity?

(Asked by: username_0 on 2012-08-03)

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.

**Tags:** cc.complexity-theory, algebra, algebraic-complexity
> **Comments:**
> **username_1**: Type Integer in Haskell is multi-precision integers, and the time complexity of addition on them naturally depends on the length of the input integers, so it is misleading to say that mappend in your Monoid instance for Integer runs in constant time.  
> **username_0**: @TsuyoshiIto  You're right, I meant to use Int.  Fixed.  
> **username_2**: Have you seen [this question](http://cstheory.stackexchange.com/questions/3074/a-category-of-np-complete-problems)?  
> **username_0**: @Kaveh I hadn't, thanks for the pointer.  From a quick read through it sounds like no one's done any category theoretic work on complexity classes themselves (and there's some debate about what that might even mean or if it's a worthwhile goal).  So I think that pretty much answers the first part of my question and just leaves any interactions between algebra and complexity.  
> **username_2**: The are a lot of interaction between algebra and complexity theory. There are even books titled "Algebraic Complexity Theory" which use and apply algebraic concepts and techniques to complexity. And there are also extensive works applying complexity theory to algebra. You have to be more specific to get an answer.  
> **username_2**: Btw, it appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).  
> **username_2**: http://math.stackexchange.com/q/178207/  
> **username_0**: @Kaveh Okay, I think I get the rules now.  
> **username_3**: How about homology of some sort?  
> **username_4**: @Kaveh Isn't the book "Algebraic Complexity Theory"  mostly about the computational complexity of algebraic operations like multiplication of polynomials?  

---

## 2 answers

### Answer by username_4 on 2015-07-22. Score: 12

> [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](http://arxiv.org/abs/1405.3311)) 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.

> **Comments:**
> **username_5**: I'd say that the composition of Turing machines is fairly clear when you think about them as abstract computer programs. The natural way to compose programs is to call one as a subprogram of another. More generally, each program is a computable in finite time and space function which accepts certain formatted input and outputs another formatted string, which can be fed into another function. It's possible that some garbage inputs will result in garbage outputs or that some function fails to execute in the allotted time and space, in which case the whole program crashes.  
> **username_5**: Obviously no all programs are composable in this way, which naturally leads us to a category of TMs. It's also likely that one should let go the notion of a time-space unlimited TM, which isn't practically feasible anyway. Is there some published notion which captures this structure?  
> **username_4**: @AntonFetisov Have you tried writing down the details? It's not pretty.  
> **username_6**: @AntonFetisov this idea of calling subprograms – ignoring any notion of inputs being of a „correct“ or „incorrect type“ – might fit into the framework of [operads](https://en.wikipedia.org/wiki/Operad).  

---

### Answer by username_7 on 2015-07-21. Score: 2

This [answer](https://cs.stackexchange.com/questions/24574/what-are-appropriate-isomorphisms-between-formal-languages/43564#43564) 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.)

> **Comments:**
> **username_7**: I made this a community wiki, because it links to my own answer to my own question, which is certainly not great. I was "cleaning" my favorites, and just writing this short answer was the easiest way to proceed.  

---

