Computational Complexity,
Abstract
According to the story, which had been picked up from the magazine Science, 'apart from its profound theoretical interest, the discovery may be applicable in weather prediction, complicated industrial processes, petroleum refining, the scheduling of workers at large factories, secret codes and many other thing'. The new York Times coverage generated substantial controversy concerning the merits of the discovery, a new algorithm for doing linear programming. Near the end of this article we will evaluate this algorithm. The new York Times story concerned the 'computational complexity' of the linear programming problem. Although computational complexity does not always make front page news, it is a very active and important research area. Its subject is the determination of the intrinsic difficulty of mathematically posed problems arising in many disciplines. The study of complexity has led to more efficient algorithms than those previously known or suspected. We illustrate some of the important ideas of computational complexity with the example of matrix multiplication. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1980
- Accession Number
- ADA089177
Entities
People
- Joseph F. Traub
Organizations
- Carnegie Mellon University