Taking It to the Limit: On Infinite Vari
β
Tirza Hirst; David Harel
π
Article
π
1996
π
Elsevier Science
π
English
β 673 KB
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, whil