Re:What would the impacts of this be for cryptogra
on
Claimed Proof That P != NP
·
· Score: 2, Informative
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.
The traveling salesman problem is NP-complete, slime molds or not. Under some conditions it can be approximated efficiently, but slime molds are not about to solve the travelling salesman problem in sub-exponential time.
In any case, using a computer is much faster than waiting a few days for a slime mold to grow.
Slashdot Mirror
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.
The traveling salesman problem is NP-complete, slime molds or not. Under some conditions it can be approximated efficiently, but slime molds are not about to solve the travelling salesman problem in sub-exponential time. In any case, using a computer is much faster than waiting a few days for a slime mold to grow.