Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 44 min ago
PreprintarXiv licencearXiv

Discrete Temporal CSPs et al

  • Lukas Pieper
Open at sourcePDFDOICite

Abstract

We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of (ℤ,<), established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of (ℤ,<) that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a P versus NP-complete dichotomy.

Related

  1. Finite-on-Top-of-Temporal CSPs in Fixed-Point Logic
    Manuel Bodirsky, Philipp A. Grzywaczyk
    arXivPreprintCC BY-SA 4.0Full textLogic & foundationsarXiv
  2. Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
    Florian Starke
    arXivPreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryarXiv
  3. Compactness Principles for CSPs and the Axiom of Chocie
    Anthony Li, Ishin Shan, Matthew Snodgrass +2
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  4. A Non-Dichotomy for CSPs of Stable ω-Categorical Structures
    Manuel Bodirsky, David Bradley-Williams, Ehud Hrushovski +1
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  5. Michell-Prager type truss structures constructed from integrable discrete power function and discrete logarithmic function
    Motoki Masada, Kentaro Hayakawa, Kazuki Hayashi +3
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{pieper2026discrete,
  title = {{Discrete Temporal CSPs et al}},
  author = {Lukas Pieper},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21967},
  eprint = {2610.21967},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21967},
}
RIS
TY  - UNPB
TI  - Discrete Temporal CSPs et al
AU  - Lukas Pieper
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21967
UR  - https://arxiv.org/abs/2610.21967
AB  - We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of (ℤ,<), established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of (ℤ,<) that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a P versus NP-complete dichotomy.
ER  -