Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 30 min ago
PreprintCC BY-NC-SA 4.0arXiv

Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)

  • Florian Starke
Open at sourcePDFDOICite

Abstract

We show that the constraint satisfaction problem of any finite conservative structure that can not pp-construct st-Con (whose CSP is NL-complete) or 3Lin2 (whose CSP is Mod2L-complete) is solved by a symmetric linear Datalog program and therefore in L.

Related

  1. (Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope
    Sebastian Pokutta
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  2. Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
    Jing Zhang, Yuan Li
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  3. Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions
    Yuan Li, Jing Zhang
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  4. Maximum principle for quasilinear SPDE’s on a bounded domain without regularity assumptions
    Laurent Denis, Anis Matoussi
    Stochastic Processes and their ApplicationsPeer-reviewedLicence not statedFull text15 citedGeneral mathematicsHAL
  5. On the spherical symmetry and finite-range assumptions of the interaction potential in the low energy study of dilute Bose gases
    Lukas Reichmann, Arnaud Triay
    arXivPreprintarXiv licenceFull textMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{starke2026conservative,
  title = {{Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)}},
  author = {Florian Starke},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.32463},
  eprint = {2609.32463},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.32463},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
AU  - Florian Starke
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.32463
UR  - https://arxiv.org/abs/2609.32463
AB  - We show that the constraint satisfaction problem of any finite conservative structure that can not pp-construct st-Con (whose CSP is NL-complete) or 3Lin2 (whose CSP is Mod2L-complete) is solved by a symmetric linear Datalog program and therefore in L.
ER  -