-1

根据维基百科,我正在尝试理解NPNP completeNP hard的概念。

如果我正确理解给定的文本:

编辑:根据大卫更正

NP == 决策问题,其答案可以在多项式时间内得到验证(给定解决方案)

NP 完成== NPNP 困难同时

NP 难== 存在一个NP 完全问题,它是多项式时间图灵可约简到它。

所以为了理解NP完整性的概念,我需要先了解NP硬度。所以我试着根据上面的说法来分析一下什么是NP难。所以我得到:

NP hard == 有一个问题是NP hardNP同时存在的,可以归结为它。但是定义中有一个循环。什么是非周期性定义?

4

1 回答 1

1

您还可以将 NP 完全定义为一个问题,这样任何 NP 问题都可以在多项式时间内简化为它。该定义应该删除您的周期。

您对 NP-hard 的定义似乎倒退了。如果某个 NP 完全问题(因此任何 NP 问题)可以在多项式时间内简化为该问题,则该问题应该是 NP 难题。

您可以在此处查看更多详细信息:http ://en.wikipedia.org/wiki/P_versus_NP_problem

于 2012-09-03T21:27:27.870 回答