ers in theoretical computer science have often migrated between industry and academia, and researchers in these sectors have often collaborated. Such mixing and travel helped infuse computing theory with an understanding of the practical problems faced by computer designers and helped establish a community of researchers with a common vocabulary.


  • 1.  

    Between 1973 and 1996, NSF funding for theoretical computer science grew from less than $2 million to almost $7 million dollars. In 1996 dollars (i.e., taking inflation into account), the NSF spent the equivalent of $6.1 million on theory in 1973, versus $6.9 million in 1996. Thus, the real increase in funding over 23 years was just 13 percent, or about 0.5 percent a year, on average.

  • 2.  

    A class of mathematical problems, usually with yes or no answers, is called "decidable" if there is an algorithm that will produce a definite answer for every problem in the class. Otherwise, the class of problems is undecidable. Turing demonstrated that no algorithm exists for answering the question of whether a Turing-machine calculation will terminate. The question might be answered for many particular machines, even mechanically. But no algorithm will answer it for all machines: there must be some machine about which the algorithm will never come to a conclusion.

  • 3.  

    Hao Wang, who began his work at Oxford University and later moved to Bell Laboratories and IBM, elucidated the sources of undecidability.

  • 4.  

    As an example of big-oh notation, the number of identical fixed-size solid objects that can be fit into a cube with sides of length L is O(L3), regardless of the size or shape of the objects. This means that for L arbitrarily large, at most L3 objects will fit (scaled by some constant).

  • 5.  

    A class of problems is said to be "tractable" when the time necessary to solve problems of the class varies at most as a power of problem size.

  • 6.  

    This problem involves figuring out the most efficient route for a salesperson to follow in visiting a list of cities. Each additional city added to the list creates a whole series of additional possible routes that must be evaluated to identify the shortest one. Thus, the complexity of the problem grows much faster than does the list of cities.

  • 7.  

    Correctness is defined as the property of being consistent with a specification.

  • 8.  

    For a more complete discussion of cryptography's growing importance, see Computer Science and Telecommunications Board (1996).

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement