13
$\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 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.

$\endgroup$
7
  • 1
    $\begingroup$ I don't think it's so weird. In general specialists from different fields don't talk to each other all that much. $\endgroup$ Commented Aug 2, 2012 at 23:02
  • 3
    $\begingroup$ 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. $\endgroup$
    – t.b.
    Commented Aug 2, 2012 at 23:40
  • 3
    $\begingroup$ Well, get started. You'll be the first! $\endgroup$
    – Will Jagy
    Commented Aug 3, 2012 at 0:04
  • 1
    $\begingroup$ cross-post on cstheory. $\endgroup$
    – Kaveh
    Commented Aug 4, 2012 at 8:50
  • 3
    $\begingroup$ Related seems geometric complexity theory, which recently has raised some attention, see e.g. this talk for an overview. $\endgroup$ Commented Jun 25, 2013 at 11:18

2 Answers 2

3
$\begingroup$

It seems that the idea of growth of groups is extremely relevant here. In the example in the question the operation may be viewed as concatenation of words, and so is very similar to the standard way in which we view the free group on $m$ generators $F(\mathbf{x}_m)$. The operation $V\circ W$ takes $O(|V|+|W|)$-time* to evaluate in $F(\mathbf{x}_m)$.

Every finitely-generated group can be constructed by taking such a (finite rank) free group $F(\mathbf{x}_m)$ and adding relators. These relators correspond to "short cuts" in our computation. For example, consider the free group $F(a)$ and add the relator $a^3=\epsilon$ (here, $\epsilon$ denotes the empty word) to obtain the group with presentation $\langle a\mid a^3\rangle$. (This group is actually cyclic of order $3$.) Now, I can evaluate $a^{100}\circ a^{34}$ to get $a^{134}$, but why would I? As I am in my group I know that $a^{100}=a$ and $a^{34}=a$ so $a^{100}\circ a^{34}=a\circ a=a^2$. The idea of growth of groups is to make sense of these "shortcuts" computationally. Roughtly, the "growth" of a group corresponds to how many group elements there are at distance $n$ from the identity element. Crucially, growth rate does not depend on the choice of generating set. Please see the above Wikipedia link for more details. However, I will leave you with some examples of groups and their growth rate (taken and amended from Wikipedia, of course!):

  • A free group with a finite rank $k > 1$ has an exponential growth rate.
  • A finite group has constant growth – polynomial growth of order $0$.
  • A group has polynomial growth if and only if it has a nilpotent subgroup of finite index. This is a massive result due to Gromov see wiki. It was one of the first results to "link" analytic behaviour of a group with its algebraic structure.
  • If M is a closed negatively curved Riemannian manifold then its fundamental group $\pi _{1}(M)$ has exponential growth rate. Milnor proved this using the fact that the word metric on $\pi_{1}(M)$ is quasi-isometric to the universal cover of $M$.
  • $\mathbb{Z}^d$ has a polynomial growth rate of order $d$.
  • The discrete Heisenberg group $H^3$ has a polynomial growth rate of order $4$. This fact is a special case of the general theorem of Bass and Guivarch that is discussed in the article on Gromov's theorem on groups of polynomial growth.
  • The lamplighter group has an exponential growth.
  • The existence of groups with intermediate growth, i.e. subexponential but not polynomial was open for many years. It was asked by Milnor in 1968 and was finally answered in the positive by Grigorchuk in 1984 (see Girgorchuk's group). This is still an area of active research.
  • The class of triangle groups include infinitely many groups of constant growth, three groups of quadratic growth, and infinitely many groups of exponential growth.

*This is an easily-computed upper bound. You can probably do something clever to reduce this though.

$\endgroup$
0
$\begingroup$

These two works may be interested.

  • J.C. Birget M.V. Sapir and E. Rips. Isoperimetric and isodiametric functions of groups. Annals of Mathematics, 156:345-466, 2002.
  • Gasperin, Anthony. Through group theory and topology, a contribution to computation and complexity theory. Diss. University of Geneva, 2014.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .