Re:Galactic Algorithm
by Gehinnn on Saturday October 05, 2019 @08:01AM
(#21165043)
How do you prove that something is faster than everything else? Was it already running in linear-time?
There aren't many non-trivial lower bounds out there, and I think they all use one of three ideas (diagonalization, crossing sequences or oracle reconstruction)!
Re:Galactic Algorithm
by cperciva on Saturday October 05, 2019 @12:21PM
(#21166335)
Sorry, I was unclear. I proved that my algorithm was faster than other known algorithms; I didn't prove that it was faster than all other possible algorithms.
There aren't many non-trivial lower bounds out there, and I think they all use one of three ideas (diagonalization, crossing sequences or oracle reconstruction)!