2019/09/11 by Libor Barto · 1 citation
Computer Science · #cs.CC
paper · pdf · doi:10.1109/lics.2019.8785671
published as 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Vancouver, BC, Canada, 2019, pp. 1-8
arxiv created 2019/09/11 · arxiv updated 2019/09/12
The fixed template Promise Constraint Satisfaction Problem (PCSP) is a recently proposed significant generalization of the fixed template CSP, which includes approximation variants of satisfiability and graph coloring problems. All the currently known tractable (i.e., solvable in polynomial time) PCSPs over finite templates can be reduced, in a certain natural way, to tractable CSPs. However, such CSPs are often over infinite domains. We show that the infinity is in fact necessary by proving that a specific finite-domain PCSP, namely (1-in-3-SAT, Not-All-Equal-3-SAT), cannot be naturally reduced to a tractable finite-domain CSP, unless P=NP.