|
|
|
|
|
|
by utopcell
359 days ago
|
|
|
The result doesn't actually apply to _all_ algorithms, only oblivious ones. Oblivious algorithms are ones where step i does not depend on decisions made in steps j < i. Almost all useful algorithms are non-oblivious, with some notable exceptions [1]. This work is a step forward towards proving the result for the general case, with little practical usage (and that's perfectly okay). [1] https://en.wikipedia.org/wiki/Sorting_network |
|
|