Definable inapproximability: new challenges for duplicator
Definable inapproximability: new challenges for duplicator
复制标题
可定义的不近似性：复印机的新挑战
DOI：
10.1093/logcom/exz022
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
Atserias A
中科院分区：
文献类型：
--
作者：
Atserias A
我们从可定义性的角度考虑优化问题逼近的困难性。对于许多困难的优化问题，众所周知，除非，没有多项式时间算法可以给出一个近似的解决方案，保证是在一个固定的常数因子的最佳。我们表明，在几个这样的情况下，没有任何复杂性理论的假设，没有算法，是在不动点逻辑计数（FPC）可以计算出一个近似的解决方案。由于近似算法（如线性或半定规划）的重要算法技术可以在FPC中表达，这就产生了通过这些方法可以实现的下限。结果是建立在一阶逻辑与计数，以分离的实例，具有高的最佳从那些具有低的最佳固定大小的实例所需的变量的数量上的下限。
We consider the hardness of approximation of optimization problems from the point of view of definability. For many-hard optimization problems it is known that, unless, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances.