{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T23:07:48Z","timestamp":1778540868861,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Royal Society Enhancement Award"},{"name":"NSERC PGS Doctoral Award"},{"name":"Royal Society University Research Fellowship"},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin et\u00a0al.\u00a0[SICOMP\u201917] proved a result known as \u201c(2+\u025b)-SAT is NP-hard.\u201d They showed that the problem of distinguishing\n            <jats:italic>k<\/jats:italic>\n            -CNF formulas that are\n            <jats:italic>g<\/jats:italic>\n            -satisfiable (i.e., some assignment satisfies at least\n            <jats:italic>g<\/jats:italic>\n            literals in every clause) from those that are not even 1-satisfiable is NP-hard if\n            <jats:italic>g\/k<\/jats:italic>\n            &lt; 1\/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus, we give a dichotomy for a natural fragment of\n            <jats:bold>promise constraint satisfaction problems<\/jats:bold>\n            (\n            <jats:bold>PCSPs<\/jats:bold>\n            ) on arbitrary finite domains.\n          <\/jats:p>\n          <jats:p>The hardness side is proved using the algebraic approach via a new general NP-hardness criterion on polymorphisms, which is based on a gap version of the Layered Label Cover problem. We show that previously used criteria are insufficient\u2014the problem hence gives an interesting benchmark of algebraic techniques for proving hardness of approximation in problems such as PCSPs.<\/jats:p>","DOI":"10.1145\/3470867","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:28:46Z","timestamp":1630524526000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["The Complexity of Promise SAT on Non-Boolean Domains"],"prefix":"10.1145","volume":"13","author":[{"given":"Alex","family":"Brandts","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}]},{"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2021,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.90"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_2_1_6_1","volume-title":"Retrieved","author":"Barto Libor","year":"2019","unstructured":"Libor Barto , Jakub Bul\u00edn , Andrei A. Krokhin , and Jakub Opr\u0161al . 2019 . Algebraic approach to promise constraint satisfaction. arXiv:1811.00970 . Retrieved June 21, 2019 from https:\/\/arxiv.org\/abs\/1811.00970. Libor Barto, Jakub Bul\u00edn, Andrei A. Krokhin, and Jakub Opr\u0161al. 2019. Algebraic approach to promise constraint satisfaction. arXiv:1811.00970. Retrieved June 21, 2019 from https:\/\/arxiv.org\/abs\/1811.00970."},{"key":"e_1_2_1_7_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Andrei Krokhin , and Ross Willard . 2017 . Polymorphisms, and how to use them. In Complexity and Approximability of Constraint Satisfaction Problems, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.) . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 1\u201344. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.i 10.4230\/DFU.Vol7.15301.i Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In Complexity and Approximability of Constraint Satisfaction Problems, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 1\u201344. DOI:https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.i"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u2019 16)","volume":"50","author":"Brakensiek Joshua","year":"2016","unstructured":"Joshua Brakensiek and Venkatesan Guruswami . 2016 . New hardness results for graph and hypergraph colorings . In Proceedings of the 31st Conference on Computational Complexity (CCC\u2019 16) (LIPIcs), Vol. 50 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 14:1\u201314:27. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CCC. 2016.14arXiv:2016\/029 10.4230\/LIPIcs.CCC.2016.14arXiv:2016 Joshua Brakensiek and Venkatesan Guruswami. 2016. New hardness results for graph and hypergraph colorings. In Proceedings of the 31st Conference on Computational Complexity (CCC\u2019 16) (LIPIcs), Vol. 50. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 14:1\u201314:27. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.14arXiv:2016\/029"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.117"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.28"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.18"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","volume":"168","author":"Brandts Alex","year":"2020","unstructured":"Alex Brandts , Marcin Wrochna , and Stanislav \u017divn\u00fd . 2020 . The complexity of promise SAT on non-Boolean domains . In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) , Vol. 168 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 17:1\u201317:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2020.17arXiv:1911.09065 10.4230\/LIPIcs.ICALP.2020.17arXiv:1911.09065 Alex Brandts, Marcin Wrochna, and Stanislav \u017divn\u00fd. 2020. The complexity of promise SAT on non-Boolean domains. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920), Vol. 168. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 17:1\u201317:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.17arXiv:1911.09065"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316300"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","volume":"132","author":"Ficak Miron","year":"2019","unstructured":"Miron Ficak , Marcin Kozik , Miroslav Ol\u0161\u00e1k , and Szymon Stankiewicz . 2019 . Dichotomy for symmetric boolean PCSPs . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) , Vol. 132 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 57:1\u201357:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2019.57arXiv:1904.12424 10.4230\/LIPIcs.ICALP.2019.57arXiv:1904.12424 Miron Ficak, Marcin Kozik, Miroslav Ol\u0161\u00e1k, and Szymon Stankiewicz. 2019. Dichotomy for symmetric boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919), Vol. 132. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 57:1\u201357:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.57arXiv:1904.12424"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/050635900"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3383-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M127731X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652134"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00076"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19670130104"},{"key":"e_1_2_1_26_1","first-page":"115","article-title":"Universal search problems (in Russian)","volume":"9","author":"Levin Leonid","year":"1973","unstructured":"Leonid Levin . 1973 . Universal search problems (in Russian) . Probl. Inf. Transm. (in Russian) 9 , 3 (1973), 115 \u2013 116 . http:\/\/www.mathnet.ru\/links\/84e4c96b64cc22a33a4bdae3d4815887\/ppi914.pdf Leonid Levin. 1973. Universal search problems (in Russian). Probl. Inf. Transm. (in Russian) 9, 3 (1973), 115\u2013116. http:\/\/www.mathnet.ru\/links\/84e4c96b64cc22a33a4bdae3d4815887\/ppi914.pdf","journal-title":"Probl. Inf. Transm. (in Russian)"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185365"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470867","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470867","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470867"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470867"],"URL":"https:\/\/doi.org\/10.1145\/3470867","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"2021-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}