论文标题
三明治以承诺限制满意度
Sandwiches for Promise Constraint Satisfaction
论文作者
论文摘要
Brakensiek和Guruswami Arxiv最近提出了承诺约束满意度问题（PCSP）：1704.01937作为研究约束满意度问题（CSP）的近似值的框架。非正式的PCSP要求区分CSP的给定实例是否具有解决方案，甚至无法满足指定的放松。当前已知的所有可拖动PCSP都可以自然地减少到可处理的CSP。 Barto Arxiv：1909.04878提出了PCSP对布尔结构的示例，该降低需要在无限结构上求解CSP。我们给出了PCSP对布尔结构的第一个示例，该示例将尺寸$ 3 $但不小的结构减少到可拖动的CSP。此外，我们研究了PCSP的性质，这些PCSP的性质将降低到线性方程系统或CSP的质量分析或多数多态性的结构上。
Promise Constraint Satisfaction Problems (PCSP) were proposed recently by Brakensiek and Guruswami arXiv:1704.01937 as a framework to study approximations for Constraint Satisfaction Problems (CSP). Informally a PCSP asks to distinguish between whether a given instance of a CSP has a solution or not even a specified relaxation can be satisfied. All currently known tractable PCSPs can be reduced in a natural way to tractable CSPs. Barto arXiv:1909.04878 presented an example of a PCSP over Boolean structures for which this reduction requires solving a CSP over an infinite structure. We give a first example of a PCSP over Boolean structures which reduces to a tractable CSP over a structure of size $3$ but not smaller. Further we investigate properties of PCSPs that reduce to systems of linear equations or to CSPs over structures with semilattice or majority polymorphism.
