Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 merge 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 semigroups. Semigroups have an associative binary operation. It's well known that operations in semigroups can be parallelized due to the associativity. For example, if there's a billion numbers we want added together, we could break the problem into 10 problems of adding 100 million numbers together, then add the results.

But parallelizing the addition operator makes sense only because it can be computed in constant time and space. What if this weren't the case? For example, lists and the append operation form a common semigroup in functional programming, but the append operator takes time and space $O(n)$.

It seems like there should be a convenient way to describe the differences between these two semigroups. In general, it seems like algebras that took into account the complexity of their operations would be very useful to computer scientists like myself.

share|improve this question
I don't think it's so weird. In general specialists from different fields don't talk to each other all that much. –  Qiaochu Yuan Aug 2 '12 at 23:02
I see no reason you couldn't take the category of computable sets and functions and tie complexity data to every morphism, e.g. $O(_)$ classifications, with general rules for making this play nice with composition. –  Kevin Carlson Aug 2 '12 at 23:35
I don't know how relevant this is to your question, but I thought Eilenberg was propagating some of this in the early 70s: ICM talk, his book. See also this work by Barr and Wells. Freyd mentions in the preface to his book that computer scientists were responsible for much of the sales. So people are aware of some of the possibilities you sketch. –  t.b. Aug 2 '12 at 23:40
Well, get started. You'll be the first! –  Will Jagy Aug 3 '12 at 0:04
Related seems geometric complexity theory, which recently has raised some attention, see e.g. this talk for an overview. –  Julian Kuelshammer Jun 25 '13 at 11:18
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.