EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

On the Complexity of Symmetric vs. Functional PCSPs

Tamio-Vesa Nakajima, Stanislav Živný

ACM Transactions on Algorithms · 2024-10-31 · 20 (4) · 1-29

DOI: 10.1145/3673655 ↗

At a glance

Journal article in ACM Transactions on Algorithms, published online on 2024-08-05. Written by Tamio-Vesa Nakajima and 1 co-authors. Cited 3 times so far (Crossref); 32 references. The full text is freely available (open access, CC BY 4.0).

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →