首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

P问题、NP问题、NPC问题

P问题属于NP问题,NPC问题属于NP问题。   2. NPC问题同时属于NP hard问题,是NP与NPhard的交集。...也就是说,问题A不比问题B难。      约化具有一项重要的性质:约化具有传递性。如果问题A可约化为问题B,问题B可约化为问题C,则问题A一定可约化为问题C。...》P问题 P是指在多项式时间能由确定型图灵机解决的问题 如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。...》NP问题 NP问题是指在多项式时间内能由非确定型图灵机解决的问题      NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。...》NP-hard问题      NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广)。

1.8K60

什么是P问题、NP问题和NPC问题

他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。...下面的内容都是在讲什么是P问题,什么是NP问题,什么是NPC问题,你如果不是很感兴趣就可以不看了。接下来你可以看到,把NP问题当成是 NPC问题是一个多大的错误。     ...简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。《算法导论》上举了这么一个例子。...如果问题A可约化为问题B,问题B可约化为问题C,则问题A一定可约化为问题C。这个道理非常简单,就不必阐述了。     ...同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。

1.5K31
领券