Skip top navigation and go to page content
National Science Foundation
Computer & Information Science
next page Mathematics Home
next page More Research Overviews
Photo, caption follows:

A graph showing the topology of one portion of the Internet, as measured by an Internet performance monitor run by the Cooperative Association for Internet Data Analysis in Herndon, Virginia, on February 2, 2002.
Credit: © 2002 The Regents of the University of California, all rights reserved. For commercial use contact:

Managing and Modeling Complexity
Often, the whole is not only bigger than the sum of its parts, but very different as well. Many structures, from biochemicals to semiconductors to weather systems, are made up of myriad simple individual components. Yet once they are aggregated, they take on collective characteristics that could not have been predicted from the components themselves. That is, these systems begin to exhibit complex behavior. Mathematics can often describe and model that complexity, and NSF supports a wide array of projects. Here are a few.

  • Logic and CPU Testing. Modern central processing units and arithmetic processors are complex devices that build upon simple rules for logic and arithmetic to implement higher-level functions through programs stored onboard as microcode. Chip makers need automated methods to test these devices, and the mathematics behind these testing methods must take into account, the complexity of the chip circuits. Such test systems are a fundamental line of defense between a chip maker and manufacturing flaws that could ruin even a large company.
  • Materials, Nanotechnology, and Proteins. Mathematical modeling of materials such as semiconductors, composites and components of nanomachines, is invaluable because the manufacturing process occurs at such a small scale that it cannot be observed directly. Many semiconductor devices are made by successive layering of different materials--a process that can lead to complexity. Mathematical ideas that improve simulation and control of fabrication have resulted in improvements worth millions of dollars.
  • Protein Activity. Mathematical models of small objects are also studied in biological topics such as folding and "docking" of proteins. Docking problems are fascinating: proteins somehow manage to connect along regions that resemble keys and locks, and that may be much smaller than the entire molecule.
  • Random Graphs. In one context, a "graph" is a network of nodes and the links between them, like a highway map. The study of randomly generated graphs is a well established part of a branch of mathematics called combinatorics. It is possible that growth patterns for a number of real-world networks, including the Internet, can be modeled using probability distributions that had not been explored previously.
  • Prime Numbers. The distribution of prime numbers (that is, those that can only be divided by themselves and by 1) is a question of large and long-standing interest in mathematics. For example, information encryption systems typically employ "keys" that are the product of two primes. The security of the system depends heavily on the fact that, so far at least, factoring a large number into its prime factors takes a very large amount of time. Understanding the distribution of primes over the numerical continuum may well reveal an unexpected complexity or repeated patterns, perhaps analogous to the periodic table in chemistry.

Deciding on the Best Choice [Next]