Accession Number:

ADA089177

Title:

Computational Complexity,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1980-07-01

Pagination or Media Count:

13.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE