查看: 9261|回复: 9

什么是NP问题？什么是完全NP问题？

字体大小: 正常放大

from911

56 主题	2 听众	110 积分

升级 5%

该用户从未签到

电梯直达

1^#

发表于 2005-1-9 19:13 |只看该作者 |正序浏览

|招呼Ta 关注Ta

谁能介绍一下他们的概念，写论文用！

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

643814196

2 主题	3 听众	24 积分

升级 20%

该用户从未签到

群组: 数模应用

群组: 中国矿业大学数学建模协会

群组: 渭南师范学院数学建模协会

群组: 数学专业考研加油站

群组: 数学建模培训课堂2

10^#

发表于 2011-7-16 17:00 |只看该作者 |招呼Ta 关注Ta

很有帮助

我也说一句

发表

使用道具举报

冰之焰

0 主题	3 听众	209 积分

升级 54.5%

TA的每日心情

	擦汗 2012-4-30 22:20

签到天数: 58 天

[LV.5]常住居民I

9^#

发表于 2011-7-16 16:56 |只看该作者 |招呼Ta 关注Ta

youdianeryun

我也说一句

发表

使用道具举报

ggyy_sun

0 主题	0 听众	16 积分

升级 11.58%

该用户从未签到

8^#

发表于 2007-5-9 21:01 |只看该作者 |招呼Ta 关注Ta

P类：被确定性图灵机在多项式（相对于问题规模）时间内判定的问题。也就是多项式时间内可解的问题。

NP类：被不确定性图灵机在多项式时间内判定的问题。换句话说，能在多项式时间内被验证的问题。注意：不一定能在多项式时间内被解决，只是被验证。

P类是NP类的子集。（红尘戏子的说法不严密）

NP-Hard问题：所有NP类的问题都规约到的问题。

NP-Complete问题：属于NP类的NPH问题。NPC是NPH和NP的交集。

即使是NPC的，有时某些问题也能够被动态规划在多项式时间内解决。这叫做pseudo-polynomial的。

strongly NPC问题：不是伪多项式的NPC问题。这类问题不存在多项式算法，除非P=NP。