Definable inapproximability: new challenges for duplicator

DOI10.1093/LOGCOM/EXZ022MaRDI QIDQ5216336zbMATH OpenOpenAlexWikidataFDO

Authors Albert Atserias, Anuj Dawar

Publication date 17 February 2020

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1806.11307

zbMATH Keywords

descriptive complexityfixed-point logic with countinghardness of approximationMAX SATvertex cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

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 P = 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.

Recommendations

• Definable Inapproximability: New Challenges for Duplicator
• New considerations of denumerability, non-denumerability, and target-seeking algorithms
• On Unapproximable Versions of NP-Complete Problems
• scientific article; zbMATH DE number 512844
• The Nonapproximability of Non-Boolean Predicates
• Some recent strong inapproximability results
• Some optimal inapproximability results
• scientific article; zbMATH DE number 1559516
• Undecidability of bisimilarity by defender's forcing
• Infinite versions of some problems from finite complexity theory

Cited in

(6)

• Definable Inapproximability: New Challenges for Duplicator
• On the Weisfeiler-Leman dimension of fractional packing
• Inapproximability of unique games in fixed-point logic with counting
• On the descriptive complexity of temporal constraint satisfaction problems
• NP-completeness by first-order and quantifier-free interpretations and related topics
• Undefinability of approximation of 2-to-2 games

This page was built for publication: Definable inapproximability: new challenges for duplicator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216336)