Is thinking about P=NP kinda like thinking about "the game"?

At least thinking about P=NP is useful for thinking about the nature of things.

Congrats on winning the game btw.

Does it actually matter in practice whether P is NP?

F... I haven't lost The Game™ in 2 years...

@Oktokolo

Not much, really. Proving that P= NP would show that a solution *exists* in P for many currently ongoing NP problems, but doesn't bring us any closer to actually *finding* that solution.

The biggest implication for everyday life that I can come up with off the top of my head is that many of the current asymmetric cryptography systems we trust now are to be considered compromised immediately, as their security is based precisely on the fact that solving the prime factorization or discrete logarithms they employ is NP.

@CoreFusionX Well, if you have a proof that shows P time for any problem in NP, it should be rather easy to make reductions for obtaining P time on other NP problems. Though in practice a runtime of O(n^5) might not be beneficial for solving actual problem instances efficiently

@CoreFusionX Having the key length in the exponent makes breaking asymmetric crypto obviously impractical for big key lengths. And having a constant in the exponent would mathematically break that crypto. But in practice, a constant exponent can still be impractically huge. So asymmetric crypto maybe could survive a proof of P = NP.

Btw, what about quantum computers? They have been praised as being able to make everything less complex to compute. So maybe they could be used to test, whether asymmetric crypto would survive P = NP...

@Oktokolo

Quantum TMs define another whole set of complexity classes, which aren't related to P nor NP.

In the specific case of prime factorization, Shor's algorithm is your go to. It *can* solve in polynomial time, but we don't have enough qubits (yet), and has other bottlenecks like quantum modexp.

But in general, there is not a blanket statement that QTM can solve all NP problems in P time.

This is obviously an oversimplification since it makes some unspoken assumptions regarding BQP and QMA (quantum equivalents to P and NP)

Take all this with a grain of salt. It's been 10+ years since I dealt with any of this, and my quantum mechanics are in a superposition of rusty and forgotten 😂