Browsing LCS Technical Memos (1974 - 2003) by Author "Karp, Richard M. Papadimitriou, Christos H."

Now showing items 1-1 of 1

    • On Linear Characterizations of Combinatorial Optimization Problems 

      Karp, Richard M. Papadimitriou, Christos H. (1980-02)
      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 ...