证明稀疏图是NP完全的

---

即使有无限的时间，也有一些计算问题是算法无法解决的。NP完全问题是指其解法未知的问题。有趣的是，如果一个NP完全问题可以在多项式时间内解决，那么所有其他NP完全问题也可以解决。

在本研究中，我们将定义稀疏图，讨论几种复杂性类、独立集，并证明稀疏图是NP完全的。

什么是稀疏图？

稀疏图是指边数有限的图。在这种情况下，边的总数远小于可能存在的边数或最大可能的边数。有向图最多只能包含n(n-1)条边，其中n表示节点数。无向图最多只能有n(n-1)/2条边。

稀疏图和稠密图之间的区别是任意的。稀疏图的边数几乎与顶点数相同，而稠密图的边数接近最大可能的边数。

复杂性类有哪些？

计算机科学中有一些问题尚未解决；这些问题被归类为复杂性类。

它是计算机理论的一个领域，关注解决任务所需的资源。

基本资源包括时间和空间，它们指的是算法解决问题需要多长时间以及需要多大的内存。

1. P类

P类中的字母P指的是多项式时间。P包含一组可以多项式时间内解决或产生结果的基于决策的问题（只有“是”或“否”答案的问题）。

多项式时间 - 我们在特定时间（例如一分钟或一小时）内根据特定输入生成输出。这被称为多项式时间。

特点

• P问题有简单的答案。

• P类包含已解决且易处理的计算问题。

• 理论上和实践上都可以解决的问题被认为是易处理的。虽然难处理的问题在实践中无法解决，但原则上可以解决。

2. NP类

NP类包含所有不能在多项式时间内解决或产生结果的基于决策的问题，但可以在多项式时间内验证其结果。NP类包含几个子集，包括P类。

请记住，“NP”并不表示“非多项式”。这个术语的意思是“非确定性多项式”。它表示将根据单个输入创建一定数量的输出。

由于非确定性算法可以解决NP问题，因此这类问题的解很难找到，尽管它们的验证很容易。可以使用图灵机在多项式时间内解决NP问题。

其他复杂性类

复杂性类	特点
NP-Hard	一些NP-hard问题属于NP，并且检查它们很耗时。
NP-完全	NP完全问题既是NP问题，也是NP-hard问题。
Co-NP	“否”答案可以在多项式时间内验证

独立集

独立顶点集定义了图的顶点的一个子集，其中任意两个顶点之间都不构成一条边。

不能被认为是另一个独立集的合法子集的独立集被称为“极大独立集”。

“最大独立集”是给定图中最大的可行独立集。

如何证明“稀疏图是NP完全的”？

证明一个问题是NP完全的需要两个步骤：

证明给定的问题属于NP类。

稀疏图是NP-Hard问题之一

通过将问题归约到另一个NP问题来证明问题的NP完全性可能具有挑战性。这就是为什么我们证明每个现有的NP完全问题都可以在多项式时间内归约到该问题。

稀疏图属于NP类

考虑一个输入G = (V, E)以及两个整数变量a和b。

检查特定解S是否满足|S| = a需要O(|V|)的时间。

为了确保连接S中每一组节点的边数不超过b，必须使用O(|V|^2)的算法。

因此，验证稀疏图解最多需要O(|V|^2)的时间，因此是多项式时间。因此，稀疏图属于NP复杂性类。

接下来，我们将证明独立集问题是NP完全的

为了确保解中的两个顶点不相邻，验证结果只需要检查解中的任意两个顶点之间是否共享一条边。使用图G(V, E)的方法，这可以在多项式时间内完成。

flag=true
For each u, v pair in the subset V':
   Make certain that both of these do not have an edge between them.
   Set flag to false and break if there is an edge.
If the flag is set to true:
   Correct Answer.
Else:
   Incorrect answer.

可以从任何独立集问题的实例创建一个团问题实例。因此，独立集问题是NP-Hard的。

输入转换

独立集将转换为稀疏图，如下所示：

"G' = G(V, E); a = k; b = 0" 

这是因为需要最大化独立集的数量

此转换将花费O(1)时间。因此，它是多项式时间的。

输出转换

The Sparse Graph solution must be converted into the Independent Set solution.

由于k = a，稀疏图解产生的集合a是维度为k的独立集。因此，独立集可以使用稀疏图的直接输出。因为不需要转换，所以它是多项式时间的。

正确性

预先考虑一个独立集S。这也指的是稀疏图，因为S的节点之间没有任何边，并且"|S| = k = a"。

稀疏图的解也是独立集（顶点之间由零条边连接，“|S| = k = a”）。

因此，稀疏图等价于独立集。

独立集是NP完全问题。因此，完全归约需要多项式时间。

因此，稀疏图也属于NP完全类别。

结论

即使是工程师也可以从理解NP完全性中获益。假设你被要求创建一个强大的算法来解决公司的一个关键问题。如果理解NP完全性并证明该问题是NP完全的，则可以自信地暗示不太可能找到多项式时间的解。如果存在多项式时间的解，那么它将解决计算机科学中的一个重大问题，许多人多年来一直在努力解决这个问题。