{"id":"arxiv/2609.38436","url":"https://arxiv.org/abs/2609.38436","tags":["math.LO","cs.CC","cs.LO"],"score":0,"title":"Karp's NP-complete problems over first-order definable structures","domain":"math.LO","source":"arxiv","authors":["Aidan Healy","Bartek Klin"],"reviews":0,"subject":"math.LO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}