pipette
ESEspañol

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

Aidan Healy, Bartek Klin

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.