Complexity classes P and NP/Talk

This question was asked on http://www.slashdot.org a little while ago, and it seems relevant here: What, if any, would be the effects of a proof that P=NP, or that P≠NP, or indeed that the question is undecidable?
- Stuart

The latter two wouldn't have any practical consequences, but it would be a big deal in the world of theoretical computer science (and the last also one in logic and mathematics). If somebody proves P=NP, then the practical consequences depend on the way they prove it. If they explicitly exhibit a polynomial algorithm for an NP complete problem, then we would know polynomial algorithms for all NP problems, and if the degrees of the involved polynomials are reasonable, that would be huge news in many fields, but is considered extremely unlikely. It's much more likely that either the polynomial has a ridiculously high degree, or that the proof wouldn't be constructive and just generally concludes P=NP without exhibiting any algorithm altogether. In those two cases, there wouldn't be any immediate practical consequences either. --AxelBoldt

I agree with your conclusion. However, it isn't really possible for there to be a nonconstructive proof of P=NP with no known algorithm. That's because the construction has already been done. I could easily give you an algorithm for, say, Travelling Salesman, whose correctness is obvious, but whose asymptotic running time is unknown. It's easy to prove that if P=NP, then my algorithm is polytime. In fact, if a linear-time algorithm for TSP exists, then my algorithm is linear time. If anyone ever publishes a "nonconstructive" proof of P=NP, the construction will already exist. This is all academic, of course. The huge multiplicative constant means none of this would have any practical value. --LC

That's very interesting. How does the construction work? --AxelBoldt