从np完全性谈起

yogy · 发表于 2007-9-3 11:13:04

从NP完全性谈起

——计算复杂性理论介绍

孙广中，万颖瑜

sungz,yywan@mail.ustc.edu.cn

yogy · 发表于 2007-9-3 11:13:29

报告内容：

•“算法”与“好的算法”
•NP完全性
•如何处理NP 完全问题
•新的计算模型与希望

yogy · 发表于 2007-9-3 11:14:49

•

P类（Polynomial)

判定问题：只有肯定和否定两种答案
–优化问题可以化作判定问题处理
•P类
–具有多项式时间算法的判定问题形成的计算复杂性类
–猜测TSP（Traveling salesman problem)不属于P（J.Edmonds 1965）

yogy · 发表于 2007-9-3 11:16:01

推荐阅读

•计算机和难解性：NP完全性理论导引（Michael R. Garey&David S. Johnson 1979)
•可计算性与计算复杂性导引 (张立昂）
•计算理论导引
•计算理论基础

yogy · 发表于 2007-9-3 11:18:38

		自动登录	找回密码
密码			注册

回复: 从np完全性谈起