NP 硬类和 NP 完全类

如果问题属于 NP，并且与 NP 中的任何问题一样困难，则该问题属于 NPC 类。如果 NP 中的所有问题都可在多项式时间内还原到该问题，则该问题是 NP难问题，即使该问题本身可能不属于 NP。

如果任何这些问题都存在多项式时间算法，则 NP 中的所有问题都可以用多项式时间求解。这些问题称为NP 完全问题。NP 完备性现象在理论和实践上都很重要。

NP 完备性的定义

如果语言B满足两个条件，则它是NP 完全的

如果一种语言满足第二个属性，但不一定满足第一个属性，则语言B被称为NP-Hard。非正式地，如果存在图灵将某个NP 完全问题A简化为B ，则搜索问题B是NP 难问题。

NP-Hard 中的问题无法在多项式时间内解决，直到P = NP。如果一个问题被证明是NPC，就没有必要浪费时间去寻找一个有效的算法来解决它。相反，我们可以专注于设计近似算法。

以下是一些 NP 完全问题，尚无已知的多项式时间算法。

以下问题是NP-Hard问题

在这种背景下，现在我们将讨论 TSP 是 NP 完全的

旅行商问题由一名推销员和一组城市组成。推销员必须从某个城市出发并返回同一城市，访问每个城市。问题的挑战是旅行推销员想要最小化旅行的总长度

要证明TSP 是 NP 完全的，首先我们必须证明TSP 属于 NP。在 TSP 中，我们找到一个游览并检查该游览是否包含每个顶点一次。然后计算旅行边缘的总成本。最后，我们检查成本是否最小。这可以在多项式时间内完成。因此TSP 属于 NP。

其次，我们要证明TSP是NP-hard的。为了证明这一点，一种方法是证明哈密顿循环≤p _TSP（我们知道哈密顿循环问题是NP完全问题）。

假设G = (V, E)是哈密顿循环的一个实例。

因此，构建了一个 TSP 实例。我们创建完整的图G ^' = (V, E ^' )，其中

$$E^{'}=\lbrace(i, j)\冒号 i, j \in V \:\:and\:i\neq j$$

因此，成本函数定义如下 -

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & 否则\end{cases}$$

现在，假设G中存在哈密顿循环h。很明显， h中每条边的成本在G ^'中为0，因为每条边都属于E。因此，h在G ^'中的成本为0。因此，如果图G具有哈密顿循环，则图G ^{' 的}周游成本为0。

^相反，我们假设G ^'的行程h最多为0。根据定义， E ^'中边的成本为0和1。因此，每条边的成本必须为0 ，因为h ^'的成本为0。因此我们得出结论h ^'仅包含E中的边。

因此，我们证明了G具有哈密顿循环，当且仅当G ^{' 的}成本之旅至多为0。TSP 是 NP 完全的。