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.

Improve this question
$\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
    Commented 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
    Commented Oct 2, 2021 at 12:50
  • $\begingroup$ Doing a Google Scholar search for papers citing Burr's paper turns out some relevant references. $\endgroup$
    – Timothy Chow
    Commented Oct 2, 2021 at 19:17
  • $\begingroup$ There is also a relevant question on the Theoretical Computer Science StackExchange. $\endgroup$
    – Timothy Chow
    Commented Oct 3, 2021 at 16:30

3 Answers 3

Reset to default
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.

Improve this answer
$\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$
    – Yoav Kallus
    Commented 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 .

Improve this answer
$\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$
    – Yoav Kallus
    Commented 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
    Commented 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$
    – Steven Stadnicki
    Commented 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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .