3 ms·

Our CS-Prof also had another interesting point: P = NP could be true without changing many things in reality. This could occur if the reduction of an NP-comple

by tetha 3y ago

Our CS-Prof also had another interesting point: P = NP could be true without changing many things in reality. This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. Something like this exists in some graph algorithms - theoretically faster algorithms exist, but in practice, they are a lot slower than the theoretically slower algorithm until completely silly graph sizes. This could turn even more frustrating if the proof was nonconstructive.

adalacelove 3y ago
Staying in the realm of polynomial complexity matrix multiplication comes to mind, where we are approaching more and more O(n^2), where O(n^3) is the naive, but more common implementation.
- shenberg 3y ago
  In terms of practical algorithms, the Strassen algorithm (O(n^2.8)) is the only one that has runtime advantages for matrix sizes that aren't enormous, and even then, it's not always used because it has two non-trivial costs: reduced numerical stability and more memory space requirements for intermediate results.
  - adgjlsfhk1 3y ago
    It actually doesn't require more memory for intermediate results (see the Strassen reloaded paper). It's more just that it's a ton of work to implement well (even compared to a regular gemm which is already hard), and the benefits only start showing up at pretty large (~4000x4000) matrices.
globular-toast 3y ago
This is similar to Knuth's reasoning for P=NP. Essentially there might be algorithms for these problems that are simply so complex that we might never know them.
Dylan16807 3y ago
> This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. You don't even need to go that far. n^8 is smaller than 2^n once you get past 44, still well in the tractable range, but encrypting something against n^8 brute force is a pretty reasonable task.
openasocket 3y ago
Another interesting take: P != NP could be true, while changing MANY things in reality. Basically all modern asymmetric cryptography in common use rely on the difficulty of either integer factoring or discrete logarithms (including discrete logarithms of elliptic curves). The problem is, none of those problems are proven to be NP-complete! Even if we proved P != NP, there could still be polynomial time algorithms for integer factoring and/or discrete logarithms.

by tetha 3y ago

adalacelove 3y ago

Staying in the realm of polynomial complexity matrix multiplication comes to mind, where we are approaching more and more O(n^2), where O(n^3) is the naive, but more common implementation.

shenberg 3y ago
In terms of practical algorithms, the Strassen algorithm (O(n^2.8)) is the only one that has runtime advantages for matrix sizes that aren't enormous, and even then, it's not always used because it has two non-trivial costs: reduced numerical stability and more memory space requirements for intermediate results.
- adgjlsfhk1 3y ago
  It actually doesn't require more memory for intermediate results (see the Strassen reloaded paper). It's more just that it's a ton of work to implement well (even compared to a regular gemm which is already hard), and the benefits only start showing up at pretty large (~4000x4000) matrices.

globular-toast 3y ago

This is similar to Knuth's reasoning for P=NP. Essentially there might be algorithms for these problems that are simply so complex that we might never know them.

Dylan16807 3y ago

> This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. You don't even need to go that far. n^8 is smaller than 2^n once you get past 44, still well in the tractable range, but encrypting something against n^8 brute force is a pretty reasonable task.

openasocket 3y ago

Another interesting take: P != NP could be true, while changing MANY things in reality. Basically all modern asymmetric cryptography in common use rely on the difficulty of either integer factoring or discrete logarithms (including discrete logarithms of elliptic curves). The problem is, none of those problems are proven to be NP-complete! Even if we proved P != NP, there could still be polynomial time algorithms for integer factoring and/or discrete logarithms.