一句话：构造可归约到大有限 CSP 的小型 Promise CSP，并给出图情形的正面结果。
对同签名关系结构 A、B，Promise CSP 判定输入是否同态映射到 A，还是不能映射到 B。已知可 tractable 的 PCSP 常经 A→C→B 归约到 CSP(C)，Barto 表明有些需无限 C。本文证明即使有限 C 存在，其规模也可任意大：对任意 n>1 和素数 p，构造大小 n、含一个 n^p 元关系的 A、B，使其经 A→C→B 归约到大小 p 的 C 上的 tractable CSP，但不能归约到更小结构；另一族对素数 p≥7 构造大小 p-1、含三元关系的 A、B，可归约到大小 p 的 C 但不能更小。对比地，若 A、B 是图且可归约到某有限有向图 C 的 tractable CSP，则 A 或 B 本身已有 tractable CSP。该工作推广了已有结果并回答了 Deng 等人的问题。
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.
@article{paperbot1662,
title = {Small Promise CSPs that reduce to large CSPs},
author = {Alexandr Kazda and Peter Mayr and Dmitriy Zhuk},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 3},
year = {2022},
doi = {10.46298/lmcs-18(3:25)2022}
}