根据维基百科,我正在尝试理解NP、NP complete和NP hard的概念。
如果我正确理解给定的文本:
编辑:根据大卫更正
NP == 决策问题,其答案可以在多项式时间内得到验证(给定解决方案)
NP 完成== NP和NP 困难同时
NP 难== 存在一个NP 完全问题,它是多项式时间图灵可约简到它。
所以为了理解NP完整性的概念,我需要先了解NP硬度。所以我试着根据上面的说法来分析一下什么是NP难。所以我得到:
NP hard == 有一个问题是NP hard 和NP同时存在的,可以归结为它。但是定义中有一个循环。什么是非周期性定义?