2026-07-29T20:08:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22773 2025-10-02T11:31:36Z ddc:004 open_access

Undefinability of Approximation of 2-To-2 Games Dawar, Anuj Molnár, Bálint Hardness of Approximation Unique Games Descriptive Complexity Fixed-Point Logic with Counting Recent work by Atserias and Dawar [Albert Atserias and Anuj Dawar, 2019] and Tucker-Foltz [Jamie Tucker-Foltz, 2024] has established undefinability results in fixed-point logic with counting (FPC) corresponding to many classical complexity results from the hardness of approximation. In this line of work, NP-hardness results are turned into unconditional FPC undefinability results. We extend this work by showing the FPC undefinability of any constant factor approximation of weighted 2-to-2 games, based on the NP-hardness results of Khot, Minzer and Safra. Our result shows that the completely satisfiable 2-to-2 games are not FPC-separable from those that are not ε-satisfiable, for arbitrarily small ε. The perfect completeness of our inseparability is an improvement on the complexity result, as the NP-hardness of such a separation is still only conjectured. This perfect completeness enables us to show the FPC undefinability of other problems whose NP-hardness is conjectured. In particular, we are able to show that no FPC formula can separate the 3-colourable graphs from those that are not t-colourable, for any constant t. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Bálint Molnár 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.16 urn:nbn:de:0030-drops-227735 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode