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

✍ Scribed by Tirza Hirst; David Harel

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 673 KB
• Volume: 53
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0060

✦ Synopsis

We define infinite, recursive versions of NP optimization problems. For example, MAX CLIQUE becomes 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 class MAX NP, and, hence, outside MAX SNP too, by showing that their infinite versions are 7 1 1 -complete. We illustrate the technique with many examples, resulting in a large number of new 7 1 1 -complete problems.