Being able to solve NP hard optimization problems would enable progress in many areas of science and technology. For example it would allow us to find poly-sized Lean proofs for theorems efficiently, since proof verification can be done in polynomial time.
It would also be amusing to annihilate nearly six decades of proofs that assume P!=NP.
Leans proof checker is not polynomial time, unfortunately. It is super exponential. Basically, because it can verify the result of any function it can prove to be total.
to depress you even more, it is consistent with everything that we know that P != NP and that cryptography does not exist. So there is a worst of both worlds, and we cannot rule it out.
Of course, if we get ridiculous polynomials it doesn't mean much in practice. People who hope for P=NP generally hope for nice polynomials O(n^3) or something like that at worst.
Being able to solve NP hard optimization problems would enable progress in many areas of science and technology. For example it would allow us to find poly-sized Lean proofs for theorems efficiently, since proof verification can be done in polynomial time.
It would also be amusing to annihilate nearly six decades of proofs that assume P!=NP.
Leans proof checker is not polynomial time, unfortunately. It is super exponential. Basically, because it can verify the result of any function it can prove to be total.
That's fine, we just change the problem from "find a lean proof of length < f(n)" to "find a lean proof that can be validated in time < f(n)".
Oh that’s unfortunate.
Could also break the basic principles underlying most encryption approaches. I would rather have my bank account not stolen and internet working
to depress you even more, it is consistent with everything that we know that P != NP and that cryptography does not exist. So there is a worst of both worlds, and we cannot rule it out.
1 reply →
I've had enough Internet for one lifetime.
As long as we also get low order polynomial solutions to important problems, it'll be worth it.
Besides, unencrypted wifi was funny.
Even if P=NP it doesn't mean that the P approach will be better than the heuristic approach we already do today.
Of course, if we get ridiculous polynomials it doesn't mean much in practice. People who hope for P=NP generally hope for nice polynomials O(n^3) or something like that at worst.