查看: 9148|回复: 9

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

字体大小: 正常放大

from911

56 主题	2 听众	110 积分

升级 5%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

zan

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

使用道具举报

Allos

13 主题	2 听众	103 积分

升级 1.5%

该用户从未签到

2^#

发表于 2005-1-17 18:25 |只看该作者 |招呼Ta 关注Ta

找本计算复杂性理论的书看看

一时半伙讲不清楚的

尤其是np

我也说一句

发表

使用道具举报

lilycang

2 主题	2 听众	63 积分

升级 61.05%

该用户从未签到

3^#

发表于 2005-1-29 22:51 |只看该作者 |招呼Ta 关注Ta

推荐ullman等写的自动机理论、语言和计算导引，张立昂的可计算性与计算复杂性导引等

我也说一句

发表

使用道具举报

fqyyong

3 主题	2 听众	134 积分

升级 17%

该用户从未签到

4^#

发表于 2005-3-17 19:12 |只看该作者 |招呼Ta 关注Ta

维数栈问题属不属于NP问题？

我也说一句

发表

使用道具举报

cyberagui

6 主题	2 听众	99 积分

升级 98.95%

该用户从未签到

5^#

发表于 2005-3-26 20:50 |只看该作者 |招呼Ta 关注Ta

这个问题虽然简单，但要说清楚它又不太好说。　还是自己去看一看书吧。　

[em04]

我也说一句

发表

使用道具举报

红尘戏子

1 主题	3 听众	91 积分

升级 90.53%

该用户从未签到

6^#

发表于 2006-10-2 12:08 |只看该作者 |招呼Ta 关注Ta

P:多项式算法

NP:不存在多项式算法，通常就是指数式算法

我也说一句

发表

使用道具举报

agi995

0 主题	0 听众	18 积分

升级 13.68%

该用户从未签到

7^#

发表于 2006-10-11 12:13 |只看该作者 |招呼Ta 关注Ta

谢谢啊

我也说一句

发表

使用道具举报

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。