Alexandr Kazda ; Peter Mayr ; Dmitriy Zhuk - Small Promise CSPs that reduce to large CSPs

lmcs:8495 - Logical Methods in Computer Science, August 22, 2022, Volume 18, Issue 3 - https://doi.org/10.46298/lmcs-18(3:25)2022
Small Promise CSPs that reduce to large CSPs

Authors: Alexandr Kazda ; Peter Mayr ; Dmitriy Zhuk

    For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases. If there exists a structure C with homomorphisms $A\to C\to B$, then PCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way. However Barto showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to finite C is possible, this structure may become arbitrarily large. For every integer $n>1$ and every prime p we give A, B of size n with a single relation of arity $n^p$ such that PCSP(A, B) reduces via a chain of homomorphisms $ A\to C\to B$ to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime $p\geq 7$ we construct A, B of size $p-1$ with a single ternary relation such that PCSP(A, B) reduces via $A\to C\to B$ to a tractable CSP over some C of size p but not over any smaller structure. In contrast we show that if A, B are graphs and PCSP(A,B) reduces to tractable CSP(C) for some finite digraph C, then already A or B has a tractable CSP. This extends results and answers a question of Deng et al.


    Volume: Volume 18, Issue 3
    Published on: August 22, 2022
    Accepted on: July 17, 2022
    Submitted on: September 17, 2021
    Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,Mathematics - Rings and Algebras,08A70, 68R07, 05C25,G.2,F.2.2

    Share

    Consultation statistics

    This page has been seen 573 times.
    This article's PDF has been downloaded 267 times.