Starting with Cook's pioneering work on NP-completeness in 1970,
polynomial complexity theory, the study of polynomial-time com
putability, has quickly emerged as the new foundation of
algorithms. On the one hand, it bridges the gap between the
abstract approach of recursive function theory and the concrete
approach of analysis of algorithms. It extends the notions and
tools of the theory of computability to provide a solid theoretical
foundation for the study of computational complexity of practical
problems. In addition, the theoretical studies of the notion of
polynomial-time tractability some times also yield interesting new
practical algorithms. A typical exam ple is the application of the
ellipsoid algorithm to combinatorial op timization problems (see,
for example, Lovasz 1986]). On the other hand, it has a strong
influence on many different branches of mathe matics, including
combinatorial optimization, graph theory, number theory and
cryptography. As a consequence, many researchers have begun to
re-examine various branches of classical mathematics from the
complexity point of view. For a given nonconstructive existence
theorem in classical mathematics, one would like to find a construc
tive proof which admits a polynomial-time algorithm for the
solution. One of the examples is the recent work on algorithmic
theory of per mutation groups. In the area of numerical
computation, there are also two tradi tionally independent
approaches: recursive analysis and numerical analysis."
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!