NP vs small P
The P vs NP conjecture has always seemed a little odd to me. Or rather the interpretation of the conjecture that any problem in P is tractable. How reassuring is to to know a problem can be solved in time less than some polynomial function of the size of the input if that polynomial has extremely high degree?
But this evening I ran across a fascinating comment by Avi Wigderson [1] that puts the P vs NP conjecture in a different light:
Very few known polynomial time algorithms for natural problems have exponents above 3 or 4 (even though at discovery the initial exponent may have been 30 or 40).
Problems in P may be more tractable in practice than in (current) theory. Wigderson's comment suggests that if you can find any polynomial time algorithm, your chances are improved that you can find a small-order polynomial time algorithm. It seems there's something deep going on here that would be hard to formalize.
Related posts- Rapidly mixing random walks on graphs
- Digital signatures with oil and vinegar
- How to solve supposedly intractable problems
[1] From his new book Mathematics and Computation