ASNP: A Tame Fragment of Existential Second-Order Logic
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary connected 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.
Details
Original language | English |
---|---|
Title of host publication | Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings |
Editors | Marcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly |
Publisher | Springer, Berlin [u. a.] |
Pages | 149-162 |
Number of pages | 14 |
ISBN (print) | 9783030514655 |
Publication status | Published - 2020 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science, Volume 12098 |
---|---|
ISSN | 0302-9743 |
Conference
Title | 16th Conference on Computability in Europe, CiE 2020 |
---|---|
Duration | 29 June - 3 July 2020 |
City | Fisciano |
Country | Italy |
External IDs
ORCID | /0000-0001-8228-3611/work/142241062 |
---|