Infinite Versions of Some Problems from Finite Complexity Theory
Jeffry L. Hirst, Steffen Lempp · Notre Dame Journal of Formal Logic · 1996
Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.