Small Promise CSPs that reduce to large CSPs
Small Promise CSPs that reduce to large CSPs
复制标题
小型承诺 CSP 可缩减为大型 CSP
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Dmitriy Zhuk
中科院分区：
文献类型：
--
作者：
Alexandr Kazda;P. Mayr;Dmitriy Zhuk
对于相同签名的关系结构A、B，Promise Constraint
满意度问题 PCSP(A,B) 询问给定的输入结构是否映射
与 A 同态或者甚至不映射到 B。我们承诺输入
恰好满足这两种情况之一。
如果存在一个具有同态$A\to C\to B$的结构C，那么
PCSP(A,B)自然简化为CSP(C)。据我们所知
易处理的 PCSP 以这种方式简化为易处理的 CSP。然而巴托表明
有限结构 A、B 上的一些 PCSP 需要求解无限 C 上的 CSP。
我们证明，即使可以减少到有限的 C，这
结构可能变得任意大。对于每个整数 $n>1$ 和每个素数
p 我们给出大小为 n 的 A、B，其元数关系为 $n^p$，这样
PCSP(A, B) 通过同态链 $ A\to C\to B$ 简化为易于处理的
CSP 覆盖某些大小为 p 的 C，但不覆盖任何更小的结构。一秒钟
一系列示例，对于每个素数 $p\geq 7$，我们构造大小为 $p-1$ 的 A、B
具有单个三元关系，使得 PCSP(A, B) 通过 $A\to C\to B$ 减少
到某个大小为 p 的 C 上的易于处理的 CSP，但不能在任何较小的结构上。在
对比我们表明，如果 A, B 是图并且 PCSP(A,B) 简化为易于处理
CSP(C) 对于某些有限有向图 C，则 A 或 B 已经具有易于处理的 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.
DOI：
10.1145/3313276.3316300
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Bulín J
通讯作者：
Bulín J