TAKING IT TO THE LIMIT - ON INFINITE VARIANTS OF NP-COMPLETE PROBLEMS

We define infinite, recursive versions of NP optimization problems. Fo r example, MAX CLIQUE becomes the question of whether a recursive grap h contains an infinite clique. The present paper was motivated by tryi ng 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 Sigma(1)(1)-complete. We illustrate the technique with many examples, resulting in a large num ber of new Sigma(1)(1)-complete problems. (C) 1996 Academic Press, Inc .