dc.contributor.author Atserias, A en dc.contributor.author Dawar, Anuj en dc.date.accessioned 2019-09-06T23:32:07Z dc.date.available 2019-09-06T23:32:07Z dc.date.issued 2019-12-31 en dc.identifier.issn 0955-792X dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/296566 dc.description.abstract We consider the hardness of approximation of optimization problems from the point of view of definability. For many~$\NP$-hard optimization problems it is known that, unless~$\PT = \NP$, 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. dc.publisher Oxford University Press dc.rights All rights reserved dc.rights.uri dc.title Definable inapproximability: New challenges for duplicator en dc.type Article prism.endingPage 1210 prism.issueIdentifier 8 en prism.publicationDate 2019 en prism.publicationName Journal of Logic and Computation en prism.startingPage 1185 prism.volume 29 en dc.identifier.doi 10.17863/CAM.43613 dcterms.dateAccepted 2019-09-03 en rioxxterms.versionofrecord 10.1093/logcom/exz022 en rioxxterms.version AM rioxxterms.licenseref.uri http://www.rioxx.net/licenses/all-rights-reserved en rioxxterms.licenseref.startdate 2019-12-31 en dc.contributor.orcid Dawar, Anuj [0000-0003-4014-8248] dc.identifier.eissn 1465-363X rioxxterms.type Journal Article/Review en pubs.funder-project-id EPSRC (EP/S03238X/1) cam.orpheus.success Tue Mar 31 10:39:56 BST 2020 - Embargo updated * cam.orpheus.counter 2 * rioxxterms.freetoread.startdate 2020-12-31
﻿