Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.16540 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.