数学建模社区-数学中国

标题: 什么是NP问题？什么是完全NP问题？ [打印本页]

作者: from911 时间: 2005-1-9 19:13
标题: 什么是NP问题？什么是完全NP问题？
谁能介绍一下他们的概念，写论文用！

作者: Allos 时间: 2005-1-17 18:25

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

一时半伙讲不清楚的

尤其是np

作者: lilycang 时间: 2005-1-29 22:51

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

作者: fqyyong 时间: 2005-3-17 19:12

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

作者: cyberagui 时间: 2005-3-26 20:50

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

[em04]

作者: 红尘戏子 时间: 2006-10-2 12:08

P:多项式算法

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

作者: agi995 时间: 2006-10-11 12:13
谢谢啊

作者: ggyy_sun 时间: 2007-5-9 21:01
P类：被确定性图灵机在多项式（相对于问题规模）时间内判定的问题。也就是多项式时间内可解的问题。

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

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

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

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

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

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

作者: 冰之焰 时间: 2011-7-16 16:56
youdianeryun

作者: 643814196 时间: 2011-7-16 17:00
很有帮助

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)