kay*_*fun 4 algorithm computer-science np-complete np-hard np
我试图理解NP-Complete和NP-Hard之间的区别.
以下是我的理解
NP-Hard问题是在多项式时间内无法解决的问题,但可以在多项式时间内验证.
NP-Complete问题是NP中的问题,也是NP-Hard问题.
以上定义是否正确？如果是这样,那么问题不是NP而是NP-Hard.难道它们不会比NP完全问题更难,说它们只能在指数时间内得到解决和验证吗？
Zhi*_*ang 15
一个NP问题(没有NP-Hard问题)是一个决策问题,可以在多项式时间内验证.也许它们在多项式时间内是可解的,因为所有问题P也都存在NP.
一个NP-complete问题是一个决策问题,所有NP问题都可以在多项式时间减少.他们是班上最难的问题NP.
的NP-hard类是类的其至少硬如所述的问题NP-complete的问题.它们不一定是决策问题.鉴于我们不知道是否,我们NP = P很难说我们是否可以NP-hard在多项式时间内验证问题.
例如,最大集团的决策问题(给图表G一个整数K,以判断是否存在至少具有K顶点的完整图表)是个NP问题.这也是NP-complete和NP-hard.但是,最大团问题(在给定图中找到最大团)不是NP或者NP-complete,因为它不是决策问题.我们可以说它是NP-hard,因为它至少与最大集团问题的决策版本一样难.
让我简单说一下。
一位教授给他的学生一个问题，并要求他们提供一个有效的算法。
第二天，他的一些聪明的学生就破解了算法来解决这个问题。它的复杂度为O(2 n )。现在，所有人都很高兴他们已经找到了解决方案的算法。一切看起来都不错。
教授对他们表示赞赏，但表示“任务还没有结束”，并挑战他们使用系统实际解决问题。
于是，他们立即尝试在系统中进行模仿。一名学生表示，他的系统速度惊人，达到 1 GIPS（每秒1000,000,000条指令），可以在几分之一秒内解决问题。因此，他们编写算法并尝试执行它。
然后他们从数据集的100 个输入开始，然后运行它。他们惊讶地发现该程序一直运行、运行、运行并且没有停止。
然后另一个学生做了数学计算，发现系统需要2 100 / 10 9秒才能解决这个问题。大约2 -40年左右。
第二天，当程序还在运行时，教授说：“很好。亲爱的同学们，这就是我们所说的NP-Hard。系统可能有一天会给出解决方案，但恐怕我们不会在那里看到它”。
但是，同样的问题，一旦产生解决方案，如果我们能够在现实的时间内验证 NP-Hard 问题的解决方案，那么它就被称为NP-Complete。例如，子集和是一个 NP 难问题。但是，一旦我们得到子集解，我们就可以在多项式时间内轻松检查它。所以它成为 NP 完全的。