Timeline for Is there a known polynomial time complexity problem with bad constants?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 13, 2023 at 23:47 | comment | added | Carmeister | You can do something similar for any problem with a large runtime. Just fix the size of the input and then any algorithm becomes O(1). I suppose chess is a nice example since it's a real-world case where we focus on a fixed problem size. Rather than something artifical like "n instances of 3SAT with 1000 variables" which would also be O(n). | |
| Nov 13, 2023 at 6:50 | comment | added | David Loeffler | Yes, that's the whole point of this example... | |
| Nov 12, 2023 at 19:20 | comment | added | gnasher729 | Now in practice (practice haha…) there are so many chess positions that the physical lookup table would be many light years in size and any lookup would take many years. | |
| Nov 12, 2023 at 10:25 | comment | added | David Loeffler | Pursuing this example further, this can even be solved in time $A * n + B$ with $A$ fairly small (but $B$ ridiculously huge): list all possible chess positions, make a table of the optimal move in all of them, and then just look up the given input positions in the table | |
| Nov 11, 2023 at 18:04 | history | answered | gnasher729 | CC BY-SA 4.0 |