主题: 从np完全性谈起
查看单个帖子
旧 2007-09-03, 11:14 AM   #3
yogy
高级会员
 
注册日期: 06-11
帖子: 1527
精华: 15
现金: 6353 标准币
资产: 6353 标准币
yogy 向着好的方向发展
默认 回复: 从np完全性谈起
•
P类（Polynomial)

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