3 ms·
> I guess when an AI proves that P!=NP, What would be the practical impacts of this discovery?
by Shank 6mo ago
> I guess when an AI proves that P!=NP,
What would be the practical impacts of this discovery?
- nine_k 6mo agoLikely all existing cryptography would become crackable, possibly some of it, very readily.
- jannyfer 6mo agoIsn’t it the opposite?
- fwip 6mo agoI think you read it backwards - that's a possible consequence of P==NP, not P!=NP.
- nine_k 6mo agoYes, I meant the equality. We already operate on the assumption that P ≠ NP, so little would change if that were proved.
- rogerrogerr 6mo ago(Assuming you mean P==NP) Would it become crackable, or just theoretically crackable? E.g. it's one thing to show it's possible to fly to Mars, it's another thing to actually do it.
- localuser13 6mo agoNot really: * It's possible - very likely even - that even if somehow P=NP, the fastest algorithm for any NP problem turns out to be something like n^1000, which is technically P, but not practical in any way. * The proof may not be constructive, so we may just know that P=NP but it won't help us actually create an algorithm in P (nitpick: technically if P=NP there's a construction to create an algorithm that solves any NP problem in P time, but it's extremely slow - for example it involves iterating over all possible programs).