Taking It to the Limit: On Infinite Variants of NP-Complete Problems

摘要

We define infinite, recursive versions of NP optimization problems. For example,Max Cliquebecomes the question of whether a recursive graph contains an infinite clique. The present paper was motivated by trying to understand what makes some NP problems highly undecidable in the infinite case, while others remain on low levels of the arithmetical hierarchy. We prove two results; one enables using knowledge about the infinite case to yield implications to the finite case, and the other enables implications in the other direction. Moreover, taken together, the two results provide a method for proving (finitary) problems to be outside the syntactic classMaxNP, and, hence, outsideMaxSNP too, by showing that their infinite versions areΣ11-complete. We illustrate the technique with many examples, resulting ?in a large number of newΣ11-complete problems.