4 ms·
Correct me if I'm wrong but (log n)^O(n) sounds like atrocious complexity?
by davidgrenier 3y ago
Correct me if I'm wrong but (log n)^O(n) sounds like atrocious complexity?
- cvoss 3y agoIt is atrocious. It's worse than exponential. But it's much better than the prior state of the art which was n^n 2^O(n). [1] The Quanta article, unfortunately, doesn't bother to report the prior complexity for comparison, despite that that's probably the single most important thing to say in order to support the claim in the article's sub-headline. [1] https://en.m.wikipedia.org/wiki/Integer_programming#Exact_algorithms_for_a_small_number_of_variables https://en.m.wikipedia.org/wiki/Integer_programming#Exact_al...