EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the Complexity of Symmetric vs. Functional PCSPs

Tamio-Vesa Nakajima, Stanislav Živný

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →