Timeline for Is there a known polynomial time complexity problem with bad constants?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2023 at 15:05 | comment | added | Yakk | While the wikipedia article is great, embellishing this answer would be good as well. Most of those are cases of polynomial exponent shaving (dropping ^x to ^x-epsilon), but not all of them (and those exceptions would be worth mentioning). Looking at the list, the Sub-Graph problem passes, and maybe TSP (as it is a better answer). And Hutter deserves an honourable explicit mention. | |
| Nov 9, 2023 at 21:44 | comment | added | Steven | I wanted to mention Hutter search but it is already in the list :) Also related: Gödel machine. | |
| Nov 9, 2023 at 21:39 | vote | accept | Santiago Armstrong | ||
| Nov 9, 2023 at 21:16 | history | answered | Inuyasha Yagami | CC BY-SA 4.0 |