Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 45 min ago
PreprintCC BY 4.0arXiv

Karp's NP-complete problems over first-order definable structures

  • Aidan Healy
  • Bartek Klin
Open at sourcePDFDOICite

Abstract

We determine the decidability of Karp's NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets with atoms or nominal sets.

Related

  1. First-order approximations of multifunctions defined implicitly by "split" feasibility problems with applications to optimization
    Amos Uderzo
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures
    Steffen van Bergerem, Martin Grohe, Charlotte Lenz +1
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  3. Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems
    Baiying Xin, Qi Deng
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  4. First-order Methods for Variational Inequality Problems with Semi-Infinite Constraints
    Dureksha Thilakasiri, Digvijay Boob
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Obtaining Game-Stationary Points for Smooth Nonconvex-Nonconcave Minimax Problems via First-Order Methods
    Mengxuan Dong, Yao Yao, Jiawei Zhang
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{healy2026karps,
  title = {{Karp's NP-complete problems over first-order definable structures}},
  author = {Aidan Healy and Bartek Klin},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38436},
  eprint = {2609.38436},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38436},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Karp's NP-complete problems over first-order definable structures
AU  - Aidan Healy
AU  - Bartek Klin
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.38436
UR  - https://arxiv.org/abs/2609.38436
AB  - We determine the decidability of Karp's NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets with atoms or nominal sets.
ER  -