On Linear Characterizations of Combinatorial Optimization Problems
Author(s)
Karp, Richard M. Papadimitriou, Christos H.
DownloadMIT-LCS-TM-154.pdf (4.181Mb)
Metadata
Show full item recordAbstract
We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP=co-NP -- a very unlikely event. We also use the recent result by Khacian to present even stronger evidence that NP-complete combinatorial optimization problems cannot have efficient generators of violated inequalities.
Date issued
1980-02Series/Report no.
MIT-LCS-TM-154