"Genius Jumps" in the Complexity of Finite Semigroups
by
Chrystopher L. Nehaniv
University of Hertfordshire, U.K.
Coauthors: John L. Rhodes

By a detailed study of maximal proper surmorphisms and maximal proper subsemigroups, the relationship between the Krohn-Rhodes complexity of a finite semigroup and the complexities of its divisors has been bounded as follows (Nehaniv & Rhodes 1997):

cpx (S) <= 2 cpx(T) + 1 for T maximally dividing S.

The complexity might more than double in a "genius jump" in going from a maximal proper subsemigroup to the whole semigroup.

To address the sharpness of the bound in general, we describe the construction of finite semigroups S_n such that for a maximal proper submsemigroup T_n of S_n

cpx (S_n) >= 2 cpx (T_n)

where the complexity of the S_n goes to infinity.

This and related results have implications for the rates of evolution of biological complexity (Nehaniv & Rhodes 1997, 1999).

References

1. B. Austin, K. Henckell, C. Nehaniv, & J. Rhodes, ``Subsemigroups and Complexity via the Presentation Lemma'', Journal of Pure & Applied Algebra, Vol. 101, No. 3, pp. 245-289, 1995.

2. C. L. Nehaniv & J. L. Rhodes, ``Krohn-Rhodes Theory, Hierarchies, and Evolution". In: B. Mirkin, F. R. McMorris, F. S. Roberts, and A. Rzhetsky, eds., Mathematical Hierarchies and Biology. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Society, Providence, pp. 29-42, 1997.

3. C. L. Nehaniv & J. L. Rhodes, ``On the Manner in which Biological Complexity May Grow'', Mathematical Computational Biology, Lectures on Mathematics in the Life Sciences, Vol. 26, American Mathematical Society, pp. 93-102, 1999.

Homepage of C. L. Nehaniv

Date received: June 7, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-43.