13
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Tony Huynh
    Oct 2, 2021 at 3:05
  • $\begingroup$ @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"). $\endgroup$
    – user101010
    Oct 2, 2021 at 12:50
  • $\begingroup$ Doing a Google Scholar search for papers citing Burr's paper turns out some relevant references. $\endgroup$ Oct 2, 2021 at 19:17
  • $\begingroup$ There is also a relevant question on the Theoretical Computer Science StackExchange. $\endgroup$ Oct 3, 2021 at 16:30

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Of course, closely related is NP-completeness and undecidability of packing and tiling with non-square shapes and no matching rules. See e.g. mathoverflow.net/questions/344559/… $\endgroup$ Oct 2, 2021 at 2:46
10
$\begingroup$

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 .

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 2, 2021 at 17:52
  • $\begingroup$ 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. $\endgroup$
    – kaya3
    Oct 3, 2021 at 22:07
  • 2
    $\begingroup$ @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.) $\endgroup$ Oct 4, 2021 at 6:19
8
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.