On the Complexity of Symmetric vs. Functional PCSPs
ACM Transactions on Algorithms · 31.10.2024 · 20 (4) · 1-29
DOI: 10.1145/3673655 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 05.08.2024. Verfasst von Tamio-Vesa Nakajima und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The complexity of the promise constraint satisfaction problem \(\operatorname{(PCSP)}(\mathbf{A},\mathbf{B})\) is largely unknown, even for symmetric \(\mathbf{A}\) and \(\mathbf{B}\) , except for the case when \(\mathbf{A}\) and \(\mathbf{B}\) are Boolean. First, we establish a dichotomy for \(\operatorname{PCSP}(\mathbf{A},\mathbf{B})\) where \(\mathbf{A},\mathbf{B}\) are symmetric, \(\mathbf{B}\) is functional (i.e., any \(r-1\) elements of an \(r\) -ary tuple uniquely determines the last one), and \((\mathbf{A},\mathbf{B})\) satisfies technical conditions we introduce called dependency and additivity . This result implies a dichotomy for \(\operatorname{PCSP}(\mathbf{A},\mathbf{B})\) with \(\mathbf{A},\mathbf{B}\) symmetric and \(\mathbf{B}\) functional if (i) \(\mathbf{A}\) is Boolean, or (ii) \(\mathbf{A}\) is a hypergraph of a small uniformity, or (iii) \(\mathbf{A}\) has a relation \(R^{\mathbf{A}}\) of arity at least three such that the hypergraph diameter of \((A,R^{\mathbf{A}})\) is at most one. Second, we show that for \(\operatorname{PCSP}(\mathbf{A},\mathbf{B})\) , where \(\mathbf{A}\) and \(\mathbf{B}\) contain a single relation, \(\mathbf{A}\) satisfies a technical condition called balancedness , and \(\mathbf{B}\) is arbitrary, the combined basic linear programming relaxation and the affine integer programming (AIP) relaxation is no more powerful than the (in general strictly weaker) \({{\rm AIP}}\) relaxation. Balanced \(\mathbf{A}\) include symmetric \(\mathbf{A}\) or, more generally, \(\mathbf{A}\) preserved by a transitive permutation group.
Zitieren
APA
Nakajima, T., & Živný, S. (2024). On the Complexity of Symmetric vs. Functional PCSPs. ACM Transactions on Algorithms, 20(4), 1-29. https://doi.org/10.1145/3673655
Vancouver
Nakajima T, Živný S. On the Complexity of Symmetric vs. Functional PCSPs. ACM Transactions on Algorithms. 2024;20(4):1-29. doi:10.1145/3673655
BibTeX
@article{Nakajima2024,
author = {Nakajima, Tamio-Vesa and Živný, Stanislav},
title = {On the Complexity of Symmetric vs. Functional PCSPs},
journal = {ACM Transactions on Algorithms},
year = {2024},
volume = {20},
number = {4},
pages = {1--29},
doi = {10.1145/3673655}
}
EUVIMED