Timeline for Undecidable infinite analogs of NP-complete problems?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2021 at 6:19 | comment | added | Steven Stadnicki | @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.) | |
| Oct 3, 2021 at 22:07 | comment | added | kaya3 | 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. | |
| Oct 2, 2021 at 17:52 | comment | added | Yoav Kallus | 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 3:03 | history | made wiki | Post Made Community Wiki by Asaf Karagila♦ | ||
| Oct 2, 2021 at 2:26 | history | edited | Steven Stadnicki | CC BY-SA 4.0 |
added 17 characters in body
|
| Oct 2, 2021 at 2:16 | history | answered | Steven Stadnicki | CC BY-SA 4.0 |