3 ms·

Even proving P=NP would not necessarily have any practical applications. Practicality is typically not a concern in complexity theory. Even some problems that h

by zests 6y ago

Even proving P=NP would not necessarily have any practical applications. Practicality is typically not a concern in complexity theory. Even some problems that have been shown to be in P are still usually solved with non-polynomial algorithms (Linear Programming).

daxfohl 6y ago
Yeah there is no guarantee any proof would even show you how to create a polynomial algorithm for some NP problem. It could just show some logical contradiction that happens if P=NP is false. Or obviously even if the proof does show you how to do it but the exponent is some insanely large number (see some of Scott Aaronson's other articles about "busy beaver numbers"), then that does not change anything practically either.
PartiallyTyped 6y ago
I disagree. If P=NP, then we could very well start searching the space of polynomial algorithms until we find something that works and discard anything that is not polynomial - which we can check apriori since the halting problem assumes we can't peak into the Turing machine, when in practice, we can.
- zests 6y ago
  Even knowing a polynomial algorithm for SAT would not have practical implications unless the algorithm has a reasonable run time. Matrix multiplication is a great example of a problem where the best known runtime complexity algorithms are not used even though for matrixes the size of the universe they would be faster.
  - PartiallyTyped 6y ago
    I don't disagree, but it may also help in getting tighter bounds on algorithms, iirc Matrix Maltiplication doesn't have a tight Omega function. Also, finding such algorithms should significantly expand our capabilities by expanding our understanding.
- kongolongo 6y ago
  Couldn't we assume P=NP and try this anyways?
  - PartiallyTyped 6y ago
    I mean, you could do that, but knowing it exists makes the search worthwhile.
jcranmer 6y ago
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).

by zests 6y ago

daxfohl 6y ago

Yeah there is no guarantee any proof would even show you how to create a polynomial algorithm for some NP problem. It could just show some logical contradiction that happens if P=NP is false. Or obviously even if the proof does show you how to do it but the exponent is some insanely large number (see some of Scott Aaronson's other articles about "busy beaver numbers"), then that does not change anything practically either.

PartiallyTyped 6y ago

I disagree. If P=NP, then we could very well start searching the space of polynomial algorithms until we find something that works and discard anything that is not polynomial - which we can check apriori since the halting problem assumes we can't peak into the Turing machine, when in practice, we can.

zests 6y ago
Even knowing a polynomial algorithm for SAT would not have practical implications unless the algorithm has a reasonable run time. Matrix multiplication is a great example of a problem where the best known runtime complexity algorithms are not used even though for matrixes the size of the universe they would be faster.
- PartiallyTyped 6y ago
  I don't disagree, but it may also help in getting tighter bounds on algorithms, iirc Matrix Maltiplication doesn't have a tight Omega function. Also, finding such algorithms should significantly expand our capabilities by expanding our understanding.
kongolongo 6y ago
Couldn't we assume P=NP and try this anyways?
- PartiallyTyped 6y ago
  I mean, you could do that, but knowing it exists makes the search worthwhile.

jcranmer 6y ago

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).