Computational complexity is a modern discipline which analyzes the inherent difficulty of a given task. A great deal of progress has been made in classifying the time and space requirements of certain combinatorial problems. The complexity classes logarithmic space, nondeterministic logarithmic space, polynomial time, and nondeterministic polynomial time have been studied extensively. Still little is known about the comparative strengths of different resources - it is yet to be proved that the above classes are not all identical. Professor Immerman has studied these classes from a mathematical viewpoint. He has examined the inherent difficulties of expressing conditions and shown that a robust alternative view of complexity ensues. This research continues work on complexity theory, concentrating on three specific areas: (1) the power of the transitive closure operator, (2) an investigation of uniformity, and (3) an investigation of the effects of altering the number of distinct variables.
