18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Aug 3 '12 at 17:44
  • $\begingroup$ @TsuyoshiIto You're right, I meant to use Int. Fixed. $\endgroup$ – Mike Izbicki Aug 3 '12 at 18:01
  • $\begingroup$ Have you seen this question? $\endgroup$ – Kaveh Aug 3 '12 at 21:51
  • $\begingroup$ @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. $\endgroup$ – Mike Izbicki Aug 4 '12 at 0:06
  • $\begingroup$ 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. $\endgroup$ – Kaveh Aug 4 '12 at 0:08
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Anton Fetisov Jul 30 '18 at 12:13
  • $\begingroup$ 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? $\endgroup$ – Anton Fetisov Jul 30 '18 at 12:14
  • $\begingroup$ @AntonFetisov Have you tried writing down the details? It's not pretty. $\endgroup$ – Martin Berger Jul 30 '18 at 23:42
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Klimpel Jul 21 '15 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.