4 ms·
It would be horrible if we had an impossible to understand, but correct, proof of P = NP that gave no hint of how to actually construct polynomial algorithms fo
by Scarblac 10y ago
It would be horrible if we had an impossible to understand, but correct, proof of P = NP that gave no hint of how to actually construct polynomial algorithms for those problems.
- curryhoward 10y agoInterestingly, there are algorithms for solving NP-complete problems which are provably polynomial time iff P = NP. So the moment P = NP is proven, we immediately know of polynomial-time algorithms for NP-complete problems. We have the algorithms today, we just don't know if they are in P. https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
- Scarblac 10y agoHuh, thanks! That's completely surprising to me. Edit: ah ok, a semi-algorithm that just tries all possible programs...