Timeline for Permutation search problems with no known $o(n!)$ algorithms
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2016 at 16:24 | comment | added | Terry Tao | Ah, right, I should have said "one-way function" instead of "hash function"; if one hashes down to a range that is much smaller than n! then one can halt as soon as one reaches the maximum of that range, which is likely to happen in subfactorial time. But if one maps to a range much larger than n! then one can't take this shortcut. | |
| Apr 8, 2016 at 14:58 | comment | added | Bryce Sandlund | @TerryTao That example is indeed contrived, but the idea of a one-way function shows there are problems that exist in the class I am thinking of! | |
| Apr 8, 2016 at 1:42 | comment | added | Terry Tao | This is a contrived example. but finding the permutation that maximises a hash function of that permutation is probably not going to have a subfactorial algorithm. | |
| Apr 7, 2016 at 23:04 | comment | added | Tony Huynh | Interesting question. I am a bit skeptical that there is an example, since usually there is some sort of dynamic program that runs in exponential time. | |
| Apr 7, 2016 at 22:30 | answer | added | Per Alexandersson | timeline score: 0 | |
| Apr 7, 2016 at 21:42 | answer | added | Stefan Kohl♦ | timeline score: 4 | |
| Apr 7, 2016 at 21:07 | history | edited | Stefan Kohl♦ | CC BY-SA 3.0 |
Added top-level tag; some language editing.
|
| Apr 7, 2016 at 18:39 | history | asked | Bryce Sandlund | CC BY-SA 3.0 |