什么是np问题,np完全问题啊

mousedh · 发表于 2004-8-19 23:10:11

什么是np问题,np完全问题啊

itmwk · 发表于 2004-8-20 08:13:54

找本图论的书或者讲算法的书就有了,或者上网搜一下

Ferrari · 发表于 2004-8-20 10:03:55

<

>我的理解
<

>p问题，时间复杂度为多项式的。比如说O（x^n）
<

>np＝非p问题，无法找到时间复杂度在x^n的问题比如说O(e^n),O(n!)

general82 · 发表于 2004-8-21 17:10:35

<

>我们学过的学多算法都是多项式时间算法，，既对规模为n的输入，算法在最坏情况下的计算时间为O(n^k)，不是所有的问题都在多项式时间内可解，，存在一些不可解的问题，如“图灵停机问题”，任何计算机不论耗费多少时间也不能截该问题，，我们把不能在多项式时间内解答的问题归为NP问题，

mousedh · 发表于 2004-8-22 20:06:43

<

>多谢各位指点,,,,

		自动登录	找回密码
密码			注-册-帐-号