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.. More details