Timeline for Can a problem be simultaneously polynomial time and undecidable?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 3, 2010 at 8:28 | comment | added | Lamine | Is there some confusion between decision problems and the computation of their solutions ? A (decision) problem on the existence of a solution of length k can be in P but compute this solution can be exponential, nay currently impossible. This is precisely due to non-constructive proof procedure. | |
| Dec 2, 2010 at 15:04 | comment | added | arsmath | This is strictly speaking true, but not really getting at the paradox that's bothering gordon-royle. One reasonable interpretation of Robertson-Seymour is that in some abstract non-constructive sense it proves the existence of a polynomial-time algorithm for a problem. To use the algorithm, you need a finite amount of data, but it's known that there's no algorithm for finding that data (Tony Huynh gives references in his answer). It's a pretty weird situation. | |
| Dec 2, 2010 at 9:36 | history | edited | Lamine | CC BY-SA 2.5 |
deleted 13 characters in body
|
| Dec 2, 2010 at 9:36 | comment | added | Lamine | Indeed ! Should not be confused between "recursive" and "recursively enumerable". Thanks. | |
| Dec 2, 2010 at 9:21 | comment | added | Ed Dean | You just want "recursive" there instead of "recursively enumerable". Plenty of things are undecidable yet r.e. The theorems of PA for instance (and more to the point, any non-recursive r.e. set). | |
| Dec 2, 2010 at 9:08 | history | answered | Lamine | CC BY-SA 2.5 |