不是NP完全的NP难题难吗？ [英] NP-hard problems that are not NP-complete are harder?

问题描述

根据我的理解，所有NP完全问题都是NP困难的，但已知某些NP困难问题不是NP完全的，而NP困难问题的难度至少与NP完全问题一样。

这是否意味着不是NP完全的NP难题更难？

解决方案

要回答此问题，您首先需要了解哪些NP难题也是NP-难题。完成。如果NP难题属于集合NP，则它是NP完整的。要属于集合NP，问题必须是

（i）决策问题，

（ii）问题的解决方案数量应该是有限的，每个解都应该是多项式长度，并且

（iii）给定一个多项式长度解，我们应该能够说出问题的答案是是/否

$ b，b

现在，很容易看到可能存在许多不属于集合NP且难以解决的NP难题。举一个直观的例子，我们需要找到实际时间表的旅行推销员的优化版本比我们只需要确定长度<= k的时间表的旅行推销员的决策版本难得多。 / p>

From my understanding, all NP-complete problems are NP-hard but some NP-hard problems are known not to be NP-complete, and NP-hard problems are at least as hard as NP-complete problems.

Is that mean NP-hard problems that are not NP-complete are harder? And how it is harder?

解决方案

To answer this question, you first need to understand which NP-hard problems are also NP-complete. If an NP-hard problem belongs to set NP, then it is NP-complete. To belong to set NP, a problem needs to be

(i) a decision problem,
(ii) the number of solutions to the problem should be finite and each solution should be of polynomial length, and
(iii) given a polynomial length solution, we should be able to say whether the answer to the problem is yes/no

Now, it is easy to see that there could be many NP-hard problems that do not belong to set NP and are harder to solve. As an intuitive example, the optimization-version of traveling salesman where we need to find an actual schedule is harder than the decision-version of traveling salesman where we just need to determine whether a schedule with length <= k exists or not.

这篇关于不是NP完全的NP难题难吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！