论文标题
ASNP：存在二阶逻辑的驯服片段
ASNP: a tame fragment of existential second-order logic
论文作者
论文摘要
合并SNP（ASNP）是存在的二阶逻辑的片段，严格包含Feder和Vardi的二元连接的MMSNP，以及Bienvenu，Ten Cate，Lutz和Wolter的二元守护单调SNP；它是表现出复杂性二分法的NP表达性子类的有前途的候选人。我们表明，只有当且仅当无限域二分法猜想中，ASNP具有复杂的二分法，这对于二元有限限制的均质结构的一阶减少的限制满意度问题。对于此类CSP，已知强大的通用代数硬度条件已知可以描述NP- hard和多项式时间可拖动CSP之间的边界。与CSP的连接还意味着可以在有限的树宽有限结构上以多项式时间进行评估每个ASNP句子。我们证明ASNP的语法是可决定的。证据依赖于以下事实：对于有限的许多禁止子结构给出的有限二进制结构类别，合并属性是可以决定的。
Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary guarded monotone SNP of Bienvenu, ten Cate, Lutz, and Wolter; it is a promising candidate for an expressive subclass of NP that exhibits a complexity dichotomy. We show that ASNP has a complexity dichotomy if and only if the infinite-domain dichotomy conjecture holds for constraint satisfaction problems for first-order reducts of binary finitely bounded homogeneous structures. For such CSPs, powerful universal-algebraic hardness conditions are known that are conjectured to describe the border between NP-hard and polynomial-time tractable CSPs. The connection to CSPs also implies that every ASNP sentence can be evaluated in polynomial time on classes of finite structures of bounded treewidth. We show that the syntax of ASNP is decidable. The proof relies on the fact that for classes of finite binary structures given by finitely many forbidden substructures, the amalgamation property is decidable.
