Richard Karp's famous 1972 paper identified 21 problems that are NP-complete, meaning they are among the hardest problems that can be solved by checking a proposed solution quickly. Classic examples include graph coloring, satisfiability of logical formulas, and finding Hamiltonian cycles. These problems are typically studied on finite inputs like graphs with a fixed number of nodes. This paper asks what happens when you allow these problems to be posed over a much richer kind of structure, where the objects being studied can include infinitely many elements drawn from some underlying set, but the structure itself is still described in a controlled, "symmetric" way using only basic equality comparisons. These are called orbit-finite sets with atoms or nominal sets.
The key twist is that when inputs can involve these infinite but symmetrically structured objects, the classical NP-completeness results no longer automatically apply. In fact, some of these problems may become undecidable, meaning no algorithm can solve them at all, even in principle. The paper systematically goes through Karp's original list of 21 problems and determines, for each one, whether it remains decidable or becomes undecidable in this new setting. This requires carefully analyzing the specific combinatorial structure of each problem and how symmetry interacts with its computational difficulty.
The results reveal a surprisingly rich landscape: the 21 problems split into different decidability categories, showing that moving from finite to orbit-finite inputs can dramatically change a problem's nature in ways that depend on its specific structure rather than just its classical complexity. This work contributes to understanding computation over infinite but structured data, which is relevant to fields like database theory, verification of software systems, and the foundations of computer science, where data often involves unbounded collections of values like identifiers or timestamps that can be compared for equality but little else.