什么是Non

2018-06-14 00:32:53

根据维基百科，我试图理解NP，NP完全和NP难的概念。

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

编辑：根据大卫纠正

NP ==决策问题，其答案可以用多项式时间来验证（给出解决方案）

NP完成 == NP和NP同时硬

NP hard ==有一个NP完全问题，它是可缩减的多项式时间Turing。

所以为了理解NP完备性的概念，我需要先了解NP硬度 。所以我试着根据上面的陈述来分析什么是NP难 。所以我得到：

NP hard ==同时存在NP hard和NP的问题，这可以归结为NP hard和NP 。但是定义中有一个循环。什么是非循环定义？

您也可以将NP-complete定义为一个问题，以便在多项式时间内减少任何NP问题。该定义应该消除你的周期。

你对NP-hard的定义似乎倒退了。如果一个NP完全问题（因此任何NP问题）可以在多项式时间内减少到NP问题，应该是一个问题是NP难的。

你可以在这里看到更多细节：http://en.wikipedia.org/wiki/P_versus_NP_problem

链接地址: http://www.djcxy.com/p/39933.html