Computational Complexity Of Discrete Optimization Problems

Preprint
Publisher Website
Google Scholar
    • preprint
      • Published in RePEc
Abstract
Recent developments in the theory of computational complexity as applied to combinatorial problems have revealed the existence of a large class of so-called NP-complete problems, either all or none of which are solvable in polynomial time. Since many infamous combinatorial problems have been proved to be NP-complete, the latter alternative seems far more likely. In that sense, NP-completeness of a problem justifies the use of enumerative optimization methods and of approximation algorithms. In this paper we give an informal introduction to the theory of NP-completeness and derive some fundamental results, in the hope of stimulating further use of this valuable analytical tool.
All Related Versions

This publication has 0 references indexed in Scilit: