欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Useful fantasies, NP≠NP∩coNP=P
时间  Datetime
2017-05-25 14:00 — 15:00 
地点  Venue
Lecture Hall, Main Library, SJTU
报告人  Speaker
Jack Edmonds
单位  Affiliation
邀请人  Host
Yaokun Wu
报告摘要  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 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 Problem". I will also explain how current cryptography challenges "NP∩coNP=P".

This talk is also invited to be a public lecture in the 9th Shanghai Conference on Combinatorics.

 

http://math.sjtu.edu.cn/conference/Bannai/2017/talk.php?20170525A