FOM: The History of Complexity Theory

[Stuart A. Kurtz]

In FOM 13 Aug 1999 15:03:02, Simpson writes:

>  > In the best case, the practitioners of subject X may respond to
>  > the critics by reforming or redirecting or recasting subject X in
>  > significant new ways, thus giving subject X a new lease on life.
>  > [SAK: citing Friedman FOM 28 Jul 1999 16:34:09]
> 
> I want to note that an excellent example of this reform process was
> seen in the 1960's with the development of computational complexity
> theory.  At the time, the theory of general recursive functions
> (``subject X'') was coming under criticism for lack of relevance to
> actual computation, because of the disavowal of time and space bounds.
> A few computer scientists and mathematicians responded by reworking
> the basic notions of recursive function theory to incorporate such
> bounds.  Thus computational complexity theory was born, and it thrives
> to this day as a mainstay of theoretical computer science.  I regard
> this reform as a wonderful chapter in the history of recursion theory.

While I agree with Simpson's characterization of complexity theory
as a mainstay of theoretical computer science, his history of the
field is so telegraphic as to be misleading.

Early theoreticians did reject "the Turing tarpit," and so proposed
finite state automata, linearly bounded automata, etc., as
mathematical models of digital computing.  But complexity theory is
not founded on their efforts.

Instead, the realization that these intrinsically limited models
could not form a satisfactory basis for a quantitative theory of
complexity lead to a reconsideration of Turing's model, and the
modern theory is based on explicit quantitative analyses of resource
utilization within Turing's framework.

It was not criticism of the theory of general recursive functions
per se that gave rise to complexity theory.  On the contrary, this
criticism had the effect of directing research away from the model
of computation that was ultimately to prove most useful.  Rejection
of the very criticism Simpson cites with approbation proved to be an
essential precondition for the development of the field.

I would like to refer any interested reader to the following
excellent history, which I consulted in preparing these remarks:

    Hartmanis, Juris. "Observations about the Development of
    Theoretical Computer Science," Annals of the History of
    Computing, Volume 3, Number 1. pp. 42-51. January 1981.

Hartmanis is regarded by most complexity theorists as founder of
their discipline, and he was party to many of the events he
recounts.

Respectfully,

Stu
---------------
Stuart A. Kurtz
Professor and Chair
Department of Computer Science
The University of Chicago

web:   http://www.cs.uchicago.edu/~stuart
email: stuart at cs.uchicago.edu
phone: (773)-702-3493
fax:   (773)-702-8487