|
从np完全性谈起
从NP完全性谈起
——计算复杂性理论介绍
孙广中，万颖瑜
sungz,yywan@mail.ustc.edu.cn
|
回复: 从np完全性谈起
报告内容：
•“算法”与“好的算法” •NP完全性 •如何处理NP 完全问题 •新的计算模型与希望 |
回复: 从np完全性谈起
•
P类（Polynomial)
判定问题：只有肯定和否定两种答案 –优化问题可以化作判定问题处理 •P类 –具有多项式时间算法的判定问题形成的计算复杂性类 –猜测TSP（Traveling salesman problem)不属于P（J.Edmonds 1965） |
回复: 从np完全性谈起
推荐阅读
•计算机和难解性：NP完全性理论导引（Michael R. Garey&David S. Johnson 1979) •可计算性与计算复杂性导引 (张立昂） •计算理论导引 •计算理论基础 |
回复: 从np完全性谈起
|
| 所有的时间均为北京时间。 现在的时间是 01:05 PM. |