Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929256740683776 |
|---|---|
| author | Wrona, Michal |
| author_facet | Wrona, Michal |
| contents | Every CSP(B) for a finite structure B is either in P or it is NP-complete but the proofs of the finite-domain CSP dichotomy by Andrei Bulatov and Dimitryi Zhuk not only show the computational complexity separation but also confirm the algebraic tractability conjecture stating that tractability origins from a certain system of operations preserving B. The establishment of the dichotomy was in fact preceded by a number of similar results for stronger conditions of this type, i.e. for system of operations covering not necessarily all tractable finite-domain CSPs.
A similar, infinite-domain algebraic tractability conjecture is known for first-order reducts of countably infinite finitely bounded homogeneous structures and is currently wide open. In particular, with an exception of a quasi near-unanimity operation there are no known systems of operations implying tractability in this regime. This paper changes the state-of-the-art and provides a proof that a chain of quasi directed Jonsson operations imply tractability and bounded width for a large and natural class of infinite structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16540 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation) Wrona, Michal Logic in Computer Science Every CSP(B) for a finite structure B is either in P or it is NP-complete but the proofs of the finite-domain CSP dichotomy by Andrei Bulatov and Dimitryi Zhuk not only show the computational complexity separation but also confirm the algebraic tractability conjecture stating that tractability origins from a certain system of operations preserving B. The establishment of the dichotomy was in fact preceded by a number of similar results for stronger conditions of this type, i.e. for system of operations covering not necessarily all tractable finite-domain CSPs. A similar, infinite-domain algebraic tractability conjecture is known for first-order reducts of countably infinite finitely bounded homogeneous structures and is currently wide open. In particular, with an exception of a quasi near-unanimity operation there are no known systems of operations implying tractability in this regime. This paper changes the state-of-the-art and provides a proof that a chain of quasi directed Jonsson operations imply tractability and bounded width for a large and natural class of infinite structures. |
| title | Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation) |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2402.16540 |