Advertisement
Published in:
2008 | OriginalPaper | Chapter
NP-Completeness
Published in: Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
For many combinatorial optimization problems a polynomial-time algorithm is known; the most important ones are presented in this book. However, there are also many important problems for which no polynomial-time algorithm is known. Although we cannot prove that none exists we can show that a polynomial-time algorithm for one “hard” (more precisely:
NP
-hard) problem would imply a polynomialtime algorithm for almost all problems discussed in this book (more precisely: all
NP
-easy problems).