13

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.

user101010
  • 5,319

3 Answers3

10

Edge matching problems, such as the Eternity II puzzle are NP-complete. Wang Tiles might be considered to be be the infinite analog, and the question of whether a set of Wang tiles can tile the plane is indeed undecidable.

Yoav Kallus
  • 5,926
  • Of course, closely related is NP-completeness and undecidability of packing and tiling with non-square shapes and no matching rules. See e.g. https://mathoverflow.net/questions/344559/reference-packing-under-translation-is-in-np – Yoav Kallus Oct 02 '21 at 02:46
10

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 .

Steven Stadnicki
  • 1,785
  • 1
    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. – Yoav Kallus Oct 02 '21 at 17:52
  • What about an infinite chessboard with infinitely many pieces, or an infinite sudoku with infinitely many givens? There can be more than one generalisation to infinite instances, and it's hard to say which generalisation should be preferred. – kaya3 Oct 03 '21 at 22:07
  • 2
    @kaya3 It's true; notably, though, (most of) the examples given in the question as well as the Wang tile example only have finite amounts of data in their questions. Even presenting the information for a chessboard with infinitely many pieces becomes non-trivial, and any such problem is likely to be at best semi-decidable just because getting through all the data will take infinite time (or, in the case where e.g. the pieces are given by TM or the like, undecidable because of the encoding itself; this issue seems to be at the heart of the Hamiltonian Path example.) – Steven Stadnicki Oct 04 '21 at 06:19
8

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.

Dan Turetsky
  • 2,678
  • 15
  • 24