Undecidable infinite analogs of NP-complete problems?

In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "doubly periodic") is undecidable. The analogous coloring problem is well known to be NP-complete (for $$k \geq 3$$ when restricted to finite graphs).

Burr also proves that certain graph-theoretic Ramsey coloring problems are undecidable for certain infinite graphs. Separately, Burr proved that the analogous Ramsey coloring problems are NP-complete when restricted to finite graphs.

Towards the end of the paper, Burr says that this is a common theme - namely, that infinite generalizations of NP-complete problems tend to be undecidable. He mentions that he does not know such an infinite analog for the traveling salesmen problem, so he did not have in mind any uniform construction that generalizes such finite problems into infinite problems.

What are some other examples of this phenomenon? I know of this paper of Freedman that tells such a story for 3-SAT, but I am not aware of other examples.

• I imagine there may even be problems which are polynomial-time solvable for finite graphs, whose infinite analogues are undecidable. Do you know of any such problems? Oct 2, 2021 at 3:05
• @TonyHuynh I unfortunately don't but I am very ignorant in the area. Freedman had proposed that the P/NP distinction could somehow be translated into a decidability/undecidability issue by "taking a limit", so I would like to hear about such problems in P (that would maybe focus the notion of "limit"). Oct 2, 2021 at 12:50
• Doing a Google Scholar search for papers citing Burr's paper turns out some relevant references. Oct 2, 2021 at 19:17
• Oct 3, 2021 at 16:30

There's at least one notable counter-example: solving the mate-in-$$poly(n)$$ problem for chess on an $$n\times n$$ board is PSPACE-complete and thus NP-hard (per https://arxiv.org/abs/2010.09271 ), but the mate-in-$$n$$ problem on an infinite board is decidable, uniformly in the input size and $$n$$. See, e.g., the discussion at Decidability of chess on an infinite board and the paper at https://arxiv.org/abs/1201.5597 .
• Another counter-example is sudoku completion. The finite version is NP-complete. An infinite ($\omega^2\times\omega^2$) sudoku board with finitely many squares filled in can be trimmed to a finite instance containing all the filled in squares, completed, and then extended. Oct 2, 2021 at 17:52
Hamiltonian Path is NP-complete; an infinite analog would have us looking for an infinite or bi-infinite such path through a computably given graph. It's easy enough to see that you can encode any $$\Sigma^0_1$$ question into either version of this problem, and so it's undecidable.