Timeline for Can a problem be simultaneously polynomial time and undecidable?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2010 at 18:42 | comment | added | Henry Towsner | I can't seem to find the paper now, but I recall reading a proof that the "level above" problem (given, I believe, a first-order predicate for the minor-closed class) is not decidable. | |
| Dec 2, 2010 at 9:36 | comment | added | ndkrempel | More to the point, the 'level above' isn't even well-defined algorithmically - how are you specifying a 'minor-closed class' as input? A fairly general way would be to specify it as a first-order predicate perhaps, and then you are likely to run into undecidability problems. Of course if you make use of R-S results and specify the minor-closed class by a finite set of excluded minors, then the 'level above' becomes rather trivial. | |
| Dec 2, 2010 at 9:21 | history | answered | ndkrempel | CC BY-SA 2.5 |