# zbMATH — the first resource for mathematics

Expressing combinatorial optimization problems by linear programs. (English) Zbl 0748.90074
The $${\mathcal P}={\mathcal NP}$$ problem is investigated. The known $$\mathcal NP$$- complete problems can be formulated as an optimization of a linear function over a convex hull of feasible solutions of the problem. Such a representation does not provide an advantage because of the exponential size of the obtained linear program (LP). The paper aims at analysing the possibility to reduce the size of the LP. Adding new variables the author proposes to transform a polytope of the LP to a specific form, named symmetric. Roughly, it is a polytope that remains “invariant” under any permutation of the initial variables. The main result is that the travelling salesman problem and the matching problem cannot be expressed by any symmetric LP with a size less than exponential.

##### MSC:
 90C35 Programming involving graphs or networks 52B12 Special polytopes (linear programming, centrally symmetric, etc.) 90C60 Abstract computational complexity for mathematical programming problems 90C27 Combinatorial optimization 90C05 Linear programming
Full Text: