Abstract

For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum.  We are able to show, in several such cases, and without any complexity theoretic assumption, that no algorithm that is expressible in counting logic (i.e. no symmetric algorithm in a general sense) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in counting logic, this yields lower bounds on what can be achieved by such methods. The results are established by showing inseparability in the logic of instances with a high optimum from those with a low optimum.  These instances are obtained by sampling from a suitable random distribution. This is joint work with Albert Atserias (UPC, Barcelona)