A* is faster at O(|E|), but it's really just an optimized Dijkstra's. Whether or not it is is the million-dollar(literally) question.Dijkstra's algorithm is a perfect solution
There's no good reason to believe prime factorisation isn't P.
By 'perfect' I meant it solves the problem perfectly, as opposed to a heuristic. You're right, it isn't optimal; I mentioned it because it's more accessible. Sort of. If you prove P=NP, you'll have proven factorisation is P. But factoring isn't NP Complete, so proving factoring is P or NP doesn't prove P=NP, nor would proving P≠NP prove factoring is NP.Whether or not it is is the million-dollar(literally) question.
There's a lot of confusion and misinformation about the P=NP problem. I think most of it stems from the fact people misunderstand what P and NP even are. They also seem to think that all these diverse NP and NP-Complete problems will suddenly become trivial if we could prove P=NP. They are somehow sucked into the fantasy that constant factors don't count in the real world because they can be ignored mathematically. Or that just because something is in NP that it would automatically have a fast enough solution that we can just write a program to get an answer in reasonable time.
And the article didn't really help. But, when dealing with the cryptography question it isn't really much about whether or not, the day after someone proves P = NP, all asymmetric crypto suddenly breaks. Most of it will probably still be usable. The problem is that polynomial problems grow much slower than, say, exponential problems, even with gigantic factors everywhere. So, the difference between a 768-bit key and a 1024-bit key, which today is astronomical(something in the 10^30 range), would be cut down to something that would probably be a little less. At some point, no matter what, there will always be a key size where the polynomial-time algorithm starts being faster than the exponential-time algorithm. And if there's one thing cryptographers don't like, it's when their cryptosystems stop working when the key size gets very large, because who says that in a hundred years we won't be using 10-billion-bit keys?There's a lot of confusion and misinformation about the P=NP problem.
Maybe. But what if someone discovers a symmetric algorithm for which the polynomial exponent is Graham's Number? That is, there are polynomial exponents for which it would take half the electrons in the universe, until the heat death of the universe, to compute relatively small n. We just have to find one.the day after someone proves P = NP, all asymmetric crypto suddenly breaks
Obviously an algorithm such as that is just as ineffective as an exponential algorithm, but it's important to know if you can turn an exponential-time algorithm into a polynomial-time algorithm because it means that, in 10 years, you might find a symmetric algorithm for which the polynomial exponent is within the realm of breakability. In the meantime, if someone finds a faster exponential-time algorithm you just double the key size.