from911 发表于 2005-1-9 19:13

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

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

Allos 发表于 2005-1-17 18:25

<P>找本计算复杂性理论的书看看</P><P>一时半伙讲不清楚的</P><P>尤其是np</P>

lilycang 发表于 2005-1-29 22:51

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

fqyyong 发表于 2005-3-17 19:12

<P>维数栈问题属不属于NP问题？</P>

cyberagui 发表于 2005-3-26 20:50

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

红尘戏子 发表于 2006-10-2 12:08

<p>P:多项式算法</p><p>NP:不存在多项式算法，通常就是指数式算法</p>

agi995 发表于 2006-10-11 12:13

谢谢啊

ggyy_sun 发表于 2007-5-9 21:01

P类：被确定性图灵机在多项式（相对于问题规模）时间内判定的问题。也就是多项式时间内可解的问题。<br/><br/>NP类：被不确定性图灵机在多项式时间内判定的问题。换句话说，能在多项式时间内被验证的问题。注意：不一定能在多项式时间内被解决，只是被验证。<br/><br/>P类是NP类的子集。（红尘戏子的说法不严密）<br/><br/>NP-Hard问题：所有NP类的问题都规约到的问题。<br/><br/>NP-Complete问题：属于NP类的NPH问题。NPC是NPH和NP的交集。<br/><br/>即使是NPC的，有时某些问题也能够被动态规划在多项式时间内解决。这叫做pseudo-polynomial的。<br/><br/>strongly NPC问题：不是伪多项式的NPC问题。这类问题不存在多项式算法，除非P=NP。<br/>

冰之焰 发表于 2011-7-16 16:56

youdianeryun

643814196 发表于 2011-7-16 17:00

很有帮助{:soso_e100:}
页: [1]
查看完整版本: 什么是NP问题？什么是完全NP问题？