有用的幻想： NP ≠ NP ∩ coNP = P。
Jack Edmonds
摘要: 我从1961年到1965 年研究课题NP 与 P 的关系，而在1966 年做出猜想
NP ≠ P 及 NP ≠ NP ∩ coNP = P。
旅行推销员问题是NP 的表述: TSP(G,T) = [图G 有条比其它周游T 便宜的周游y]。
我于1961年兴奋不已地去证明TSP(G,T) 是coNP，想法是找到一组不等式的NP描述，其解集是G 中周游的所有0,1 关联向量的凸包。
但我失败了，因此在1966 年我就猜想TSP 不属于 P。不过这些想法却表明多种其它问题属于 P，包括中国邮递员问题。
我还将解释当前的密码学怎样挑战 "NP ∩ coNP = P"。
Useful Fantasies, NP ≠ NP ∩ coNP = P
Jack Edmonds
Abstract: I spent from 1961 to 1965 on the subject NP versus P, and in 1966 made the conjectures, NP ≠ P and NP ≠ NP ∩ coNP = P.
The 'Traveling Salesman Problem' is the NP predicate:
TSP(G,T) = [there is a y, which is a tour in G cheaper than tour T in G].
I became excited in 1961 to show that TSP(G,T) is coNP by finding an NP description of a set of inequalities whose solution set is the convex hull of all the 0,1 incidence vectors of tours in G.
I failed, and so in 1966 I conjectured that TSP is not in P.
The ideas did however show various other problems to be in P including the "Chinese Postman's Problem".
I will also explain how current cryptography challenges "NP ∩ coNP = P".
http://www.math.uiuc.edu/documenta/vol-ismp/34_pulleyblank-william.pdf
https://www.zib.de/groetschel/pubnew/blossom.pdf
http://www.mathopt.org/Optima-Issues/optima97.pdfhttps://web.stanford.edu/~alroth/papers/kidneys.JET.2005.pdf
