Re:My survey article on P vs. NP (2017)
by jcranmer on Tuesday March 23, 2021 @11:45AM
(#26556384)
When most people are taught algorithms, it's done so in a way that seems to emphasize that algorithms in "P" are very fast--I doubt many people have encountered an algorithm worse than O(n^3) that's still polynomial--and the "NP" algorithms are very slow, and this gives strong rise to a solution in "P" must necessarily be better than one that is "NP". Even when complexity classes are introduced, and there's a segment on "you know, you're ignoring constant factors which could be really big," there's still no practical experience with cases that do have big constant factors.
Let me give an example where such a case exists. In 2005, a paper came out finding an algorithm for determining undirected graph connectivity in log space, which means you can't keep an unbounded stack of nodes that you have visited (as the trivial depth-first or breadth-first search algorithms do). This algorithm relies on converting the input graph using an "expander graph," basically replacing every node with an instance of a graph. When I computed how large an expander graph had to be, I found that the smallest one was ... 3^65536. It's still a constant factor, but it's larger than the number of atoms in the universe. This kind of constant factor isn't unusual for combinatorics problems (this is the same kind of space where Graham's number comes up).
My suspicion is that if P=NP, it's likely to be so only via this kind of crazy combinatorial input, which is to say, the P algorithm is completely impractical.
Outside of combinatorial algorithms, there are several other cases where the asymptotically faster algorithms are generally disfavored due to practical concerns: primality testing (AKP is a P algorithm, but slower in practice); matrix multiplication (we keep finding better exponents, but the dominant algorithm remains Strassen, and even then, that's only going to be used for distributed matrix multiplication). You mention linear programming, but my understanding is that interior point methods are generally preferred in modern implementations over simplex methods, the former being polynomial and the latter exponential (although very often polynomial in practice--another great example of typical case being far faster than worst case).
Let me give an example where such a case exists. In 2005, a paper came out finding an algorithm for determining undirected graph connectivity in log space, which means you can't keep an unbounded stack of nodes that you have visited (as the trivial depth-first or breadth-first search algorithms do). This algorithm relies on converting the input graph using an "expander graph," basically replacing every node with an instance of a graph. When I computed how large an expander graph had to be, I found that the smallest one was ... 3^65536. It's still a constant factor, but it's larger than the number of atoms in the universe. This kind of constant factor isn't unusual for combinatorics problems (this is the same kind of space where Graham's number comes up).
My suspicion is that if P=NP, it's likely to be so only via this kind of crazy combinatorial input, which is to say, the P algorithm is completely impractical.
Outside of combinatorial algorithms, there are several other cases where the asymptotically faster algorithms are generally disfavored due to practical concerns: primality testing (AKP is a P algorithm, but slower in practice); matrix multiplication (we keep finding better exponents, but the dominant algorithm remains Strassen, and even then, that's only going to be used for distributed matrix multiplication). You mention linear programming, but my understanding is that interior point methods are generally preferred in modern implementations over simplex methods, the former being polynomial and the latter exponential (although very often polynomial in practice--another great example of typical case being far faster than worst case).