$$ \newcommand{\P}{\text{P}} \newcommand{\EdmondsP}{\text{EdmondsP}} \newcommand{\NP}{\text{NP}} \newcommand{\coNP}{\text{coNP}} \newcommand{\BQP}{\text{BQP}} $$

I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (1) It is a legitimate mathematical possibility, and (2) I do not know.


Jack Edmonds, Optimum Branchings, J. Res. Natl. Bur. Stand. 71B, 233-240 (1967).

I have seen this quote many times (it appears in ‎Papadimitriou and Arora and Barak) but I haven’t read the source till today. I highly recommend anything by Edmonds, he is awesome. If you want to read just one paper: check out Paths, Trees, and Flowers.

If you are wondering, I still don’t believe that $\P = \NP \cap \coNP$. On the other hand, I wouldn’t be surprised if every combinatorial problem that is currently in $\NP \cap \coNP$—you could call this class $\EdmondsP$—turns out to be in $\P$. $\EdmondsP$, for instance, would include graph isomorphism, which I strongly believe is in $\P$. Also, if you are wondering, why this does not imply $\P = \NP \cap \coNP$—after all, if all combinatorial problems in $\NP$ are in $\P$, then $\P=\NP$—it is because we don’t believe that $\NP \cap \coNP$ has complete problems (Sipster constructed a relativized world where this holds.)

Added on May 11, 2019: I heard Jack Edmonds talk about this at the CookSymposium. I admire him a lot more now. On a side note, a debate between Edmonds and Sipser broke out at the conference about the progress towards proving $\P \neq \NP$; you can see it for yourself here (the debate starts at 10:00.) I used be in Sipster’s camp, but now I am squarely in Edmonds’s camp: the point of complexity theory is to inform real world decisions. It doesn’t matter whether $\P = \NP$ or not if we have an efficient (in the real world) algorithm for SAT.