Timeline for Undecidable infinite analogs of NP-complete problems?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2021 at 16:30 | comment | added | Timothy Chow | There is also a relevant question on the Theoretical Computer Science StackExchange. | |
| Oct 2, 2021 at 19:17 | comment | added | Timothy Chow | Doing a Google Scholar search for papers citing Burr's paper turns out some relevant references. | |
| Oct 2, 2021 at 12:50 | comment | added | user101010 | @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 7:32 | history | became hot network question | |||
| Oct 2, 2021 at 3:05 | comment | added | Tony Huynh | 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:03 | history | made wiki | Post Made Community Wiki by Asaf Karagila♦ | ||
| Oct 2, 2021 at 2:16 | answer | added | Steven Stadnicki | timeline score: 10 | |
| Oct 2, 2021 at 2:01 | answer | added | Dan Turetsky | timeline score: 8 | |
| Oct 1, 2021 at 23:59 | answer | added | Yoav Kallus | timeline score: 10 | |
| Oct 1, 2021 at 23:31 | history | asked | user101010 | CC BY-SA 4.0 |