ASNP: a tame fragment of existential second-order logic
From MaRDI portal
Publication:6333329
DOI10.1007/978-3-030-51466-2_13arXiv2001.08190MaRDI QIDQ6333329FDOQ6333329
Authors: Manuel Bodirsky, Simon Knäuer, Florian Starke 
Publication date: 22 January 2020
Abstract: 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.
This page was built for publication: ASNP: a tame fragment of existential second-order logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333329)
