Shocking though it may be, if you say "complexity" to the average mathematician, particularly to the kind of mathematician called a theoretical computer scientist, he will not first think about wreath products of semigroups! Computational Complexity, the study of the computational resources required to solve certain problems, has earned so solid place in the mathematical firmament that the foundation offering a million-dollar bounty for the solution to the Riemann Hypothesis has put the same price on the head of the P=?NP problem.

While Rhodes never did research in this area, there are some fascinating points of contact between his work and a number of important questions in computational complexity theory. In this talk I will survey some of these connections.

We'll begin with a 1965 theorem of Maurer and Rhodes on the computational power of simple non-abelian groups, and its rediscovery, more than twenty years later, by Barrington. This result implies that computation of products in finite semigroups is, in one sense, PSPACE complete, and, in another sense, complete for the circuit complexity class NC1. This leads to a natural parametrization of circuit complexity problems based on finite semigroups and the Krohn-Rhodes theorem. It appears as though simple non-abelian groups have more computational power in this setting than solvable monoids (i.e., iterations of counters), but no one knows for sure.

The second half of the talk will begin with a theorem of Straubing and Therien characterizing, in model-theoretic terms, the product variety DA* G_sol. This result has some striking parallels with a theorem of Toda on the surprising power of modular counting in a computational-complexity setting. We will explore these parallels, and propose some problems that grow out of them.

In keeping with the spirit in which this conference was conceived, the announcement of carefully stated and rigorously demonstrated results will be eschewed in favor of sweeping generalizations and reckless conjecture.