Is it a good thing for P=NP to be true?
P!=NP should be a physical law.
The universe would be fundamentally different if it were true.
>>7943295
>I talk about thinks no one knows as if I knew them and my word was fact
you're an idiot
>algorithm for linear-speed factoring found
>all cryptosystems fail
>banking system collapses due to mass theft
>internet is doomed as a place to actually do anything related to the real world because of no privacy and security
>anonymity and full information sharing only
many cons, one pro
>>7943074
If P=NP is true, it probably doesn't matter.
There's this idea that P means "tractable" and anything higher than P means "intractable", but it's not hard to produce examples of P algorithms you would never use and exponential algorithms that perform reasonably well for practical sizes.
P will always outperform exponential for some finite problem size, but that problem size can be far outside the realm of the relevant.
If P can be bad and exponential can be good, then NP can equal P and all the problems we have trouble are proving can be solved in P can still be intractable. It might just be that P seemed to mean "tractable" because it's relatively easy for humans to think of P algorithms for tractable problems.
Complexity classes are a silly part of computer science. It's something that's relatively easy to determine about an algorithm without reference to the specific hardware you're running it on or making many decisions about what sorts of hardware should be possible, so it was studied as an area that was saying *something* mathematically rigorous about algorithms and was easy to make progress in, without regard to the fact that it is of no clear value.
>>7943331
>Algorithm for linear factorization found
>Crypto systems at risk
>It'll still take a few months to get an actual implementation working
>By which point everyone's switched to Supersingular elliptic curve isogeny
>Crisis averted before it was ever a crisis.
>>7943432
You didn't understand the post at all.
It's not "it will take time to develop an implementation", it's "the constants for the polynomial are huge".
See the Matrix Multiplication problem on why O(n^2) can be infinitely worse than O(n^3). Imagine that in a bigger scale in O(n^k) vs O(e^n)
>>7943422
>except for the silly interpretation on the value of studying complexity
I just went over how identifying the complexity class of an algorithm doesn't tell you anything useful about it.
The whole study of complexity classes is based on throwing away highly pertinent information. I don't believe it has any potential to be anything other than misleading.
>>7943463
>academic topics are not relevant to the real world because of X
now where have I heard this argument before
>>7943463
Complexity is useful to know when the input size is arbitrarily large.
>>7943515
The input size is never "arbitrarily large", it is always within some finite limit.
Furthermore, the amount of computation feasible is always subject to some finite limit.
>>7943442
It's not even the constants in front of something, it could be the powers too. [math]O(n^{1000^{1000}})[/math] is still polynomial, but would grow pretty horribly, even when looking at it in big-O and not considering any constants.
