Complexity Theory Retrospective

I can begin no more eloquently than by quoting the master himself:

The systematic study of computational complexity theory has developed into one of the central and most active research areas of computer science. It has grown into a rich and exciting mathematical theory whose development is motivated and guided by computer science needs and technological advances. At the same time, it is clear that complexity theory deals with the quantitative laws of computation and reasoning, is concerned with issues and problems of direct interest to many other disciplines as well. It is quite likely that in the overall impact of computer science on our thinking, complexity theory will be recognized as one of the most influential intellectual contributions.²

I wish to commend the organizing committee for the 1988 Structures Symposium on their plan to honor Juris Hartmanis with this series of talks on his career². This is a very appropriate tribute since complexity theory is now approximately 25 years old and Juris has been a prime mover in the field throughout its history. I was privileged to have worked with Hartmanis during the early period of his complexity research, and I am grateful for this opportunity to reminisce about this time period and the beginnings of complexity.

In January, 1988, Alan Selman called and asked me to talk at the 3rd Annual Structures Conference about “Juris Hartmanis: The Middle Years”. Somehow I forgot that a talk in June implies a written paper in March—hence the very preliminary nature of that paper. It is almost two years later and I feel that I am still working on a preliminary version. I also forgot just how much my views about research and about computer science as a discipline were directly inherited from my supervisor. I interpreted the “middle years” to be the years from 1965 (when Juris came to Cornell as Chairman of a newly formed Computer Science Department) until 1978 (when the SIAM monograph [JHa78] appears). Given Juris’ energy and enthusiasm for research, I fully expect that in another twenty years we will be doing this again, by which time the “middle years” will have become part of the “early years”. So I chose a title which I think better suggests the profound impact Juris Hartmanis has had on our discipline. Beyond his seminal and ongoing contributions to the field of complexity, Hartmanis was able to use his research reputation not only to develop a department but, moreover, to strongly influence the direction of computer science as a distinct discipline.

In this paper we survey Juris Hartmanis’ contributions to isomorphism problems. These problems are primarily of two forms. First, isomorphism problems for restricted programming systems, including the Hartmanis-Baker conjecture that all polynomial time programming systems are polynomially isomorphic. Second, the research on isomorphisms, and particularly polynomial time isomorphisms for complete problems for various natural complexity classes, including the Berman-Hartmanis conjecture that all sets complete for NP under Karp reductions are polynomially isomorphic. We discuss not only the work of Hartmanis and his students on these isomorphism problems, but we also include a (necessarily partial and incomplete) discussion of the the impact which this research has had on other topics and other researchers in structural complexity theory.

In this paper we ask the question, “What must be added to first-order logic plus least-fixed point to obtain exactly the polynomial-time properties of unordered graphs?” We consider the languages L _k consisting of first-order logic restricted to k variables and C _k consisting of L _k plus “counting quantifiers”. We give efficient canonization algorithms for graphs characterized by C _k or L _k . It follows from known results that all trees and almost all graphs are characterized by C ₂.

In this paper we discuss the effect that self-reducibility properties have on the analysis of complexity classes. We begin by reviewing some of the more elementary results for readers unfamiliar with the field, and then we discuss some recent results and directions where self- reducibilities have been useful. Throughout, we focus on the question of when self-reducibility properties cause sets, or classes of sets, to have lower complexity than might otherwise be expected. This paper is an attempt to provide an overview of known results and suggest unifying concepts. By doing so we suggest that a continuing systematic study of the relationship between the internal structure of a set and the computational complexity of a set is in order.

The notion of NP-completeness has cut across many fields and has provided a means of identifying deep and unexpected commonalities. Problems from areas as diverse as combinatorics, logic, and operations research turn out to be NP-complete and thus computationally equivalent in the sense discussed in the next paragraph. PSPACE-completeness, NEXP-completeness, and completeness for other complexity classes have likewise been used to show commonalities in a variety of other problems. This paper surveys investigations into how strong these commonalities are.

This exposition gives a brief introduction to the main ideas of Kolmogorov complexity that have been useful in the area of computational complexity theory. We demonstrate how these ideas can actually be applied and provide a detailed survey of the abundant applications of this elegant notion in computational complexity theory. (Note : Preliminary versions of parts of this paper appeared in: Proc. 3rd IEEE Structure in Complexity Theory Conference, Computer Society Press, Washington D.C., 1988, pp. 80–102; and Uspekhi Mat. Nauk, 43:6 (1988), pp. 129–166 (in Russian).)

In this overview, various applications and variations of counting in structural complexity theory are discussed. The ability of exact counting is shown to be closely related with the ability of nondeterministic complementation. Relations between counting classes and classes requiring unique or few accepting computations are revealed. Further, approximate counting and relativized results are discussed.