Definable inapproximability: new challenges for duplicator
Definable inapproximability: new challenges for duplicator
Abstract We consider the hardness of approximation of optimization problems from the point of view of definability. For many $\textrm{NP}$-hard optimization problems it is known that, unless $\textrm{P} = \textrm{NP} $, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. …