文章目录

前言

一、布尔可满足性问题

二、每子句至多3个变量的布尔可满足性问题（3-SAT）

三、0-1整数规划（0-1 integer programming）

四、Set packing（Set packing）

五、最小顶点覆盖问题（Vertex cover）

六、集合覆盖问题（Set covering）

七、Feedback node set

八、Feedback arc set

九、有向哈密顿循环（Directed Hamiltonian cycle）

十、无向哈密顿循环（Undirected Hamiltonian cycle）

十一、图着色问题（Chromatic number）

十二、分团覆盖问题（Clique cover）

十三、精确覆盖问题（Exact cover）

十四、Hitting set（Hitting set）

十五、Steiner tree（Steiner tree）

十六、三维匹配问题（3-dimensional matching）

在这里插入图片描述

十七、背包问题（Knapsack）

十八、Job sequencing（Job sequencing）

十九、划分问题（Partition）

二十、最大割（Max cut）

二十一、分团问题（Clique，参考独立集）

前言

P问题：可以在多项式的时间里找到解决它的算法的问题。

NP问题：可以在多项式的时间里验证一个解的问题。

NPC问题：是一个NP问题，并且所有的NP问题都可以约化到它。

NP-Hard问题：满足NPC问题定义的第二条但不一定要满足第一条。

一、布尔可满足性问题

问题描述： 由 N个布尔变元X1，X2，X3…Xn，和M个布尔连接符（如：与、或、非、蕴含、等价…）构成的布尔表达式F，如果存在一组布尔变元和布尔连接符实例，判别F输出为1，则为可满足。

证明过程： 1.证明SAT是NP问题： 对于给定的布尔表达式和一个可能的赋值，可以在多项式时间内验证这个赋值是否使得表达式为真。这个验证过程只需要简单地计算表达式的值即可，因此SAT属于NP类问题。

2.证明SAT问题至少和某个已知的NPC问题一样难： 给定一个3SAT问题，可以将每个子句拆分成一个或多个布尔表达式，每个表达式对应于3SAT中的一个子句。如果可以在多项式时间内找到一个赋值使得原始3SAT问题可满足，则相应的SAT问题也可满足；反之亦然。）

二、每子句至多3个变量的布尔可满足性问题（3-SAT）

问题描述 3SAT问题是一个经典的布尔可满足性问题，也是计算理论中一类NP完全问题的代表。3SAT问题是指给定一个由布尔变量、逻辑符号（如与、或、非）和小括号构成的逻辑公式，其中每个子句由三个布尔变量或者其否定构成，并且整个公式是用与逻辑符号连接的。问题的目标是确定是否存在一组布尔变量的赋值，使得整个公式为真。 证明过程： 1.证明3SAT是NP问题 要证明3SAT属于NP类，我们需要证明给定一个3SAT公式和一个赋值，我们可以在多项式时间内验证该赋值是否满足公式。具体步骤如下：

给定一个布尔公式，该公式由多个子句组成，每个子句最多包含3个字面（变量或它们的否定）。 给定一个赋值，我们可以逐个检查每个子句，看是否至少有一个字面为真。 如果所有子句都满足，则该赋值是可满足的；否则，不是可满足的。 由于每个子句最多包含3个字面，验证每个子句的时间是常数级别，因此整个验证过程的时间复杂度是多项式级别的。 因此，3SAT属于NP类。

2.证明将3SAT问题至少和某个已知的NPC问题一样难 要证明3SAT是NP完全问题，我们需要证明任何一个NP问题都可以在多项式时间内归约到3SAT问题。我们从SAT问题出发，将其多项式时间归约到3SAT问题。

将一般的SAT公式转换为3SAT公式，将每个子句分解为不超过3个符号的子句： 如果子句已经包含1个或2个符号，则我们可以通过添加重复的符号来扩展成3个符号。例如，子句(x1)可以转换为(x1 ∨ x1 ∨ x1)，子句(x1 ∨ x2)可以转换为(x1 ∨ x2 ∨ x2)。 将超过3个符号的子句拆分为多个3字面子句： 对于超过3个符号的子句，我们可以引入新的辅助变量，将其拆分成多个3符号子句。例如，对于子句(x1 ∨ x2 ∨ x3 ∨ x4)，我们可以引入一个新的辅助变量y1，将其转换为： (x1 ∨ x2 ∨ y1) ∧ (¬y1 ∨ x3 ∨ x4) 这种方法可以保证每个子句都被转换为3个符号子句，并且整个转换过程在多项式时间内完成。因此，我们可以将任意的SAT问题多项式时间归约为3SAT问题。

三、0-1整数规划（0-1 integer programming）

问题描述 01整数规划问题是一类特殊的整数规划问题，其中所有决策变量的取值只能为0或1。这类问题在组合优化、计算机科学、运筹学等领域中非常常见，例如在网络流、资源分配、任务调度等实际问题中都有应用。给定一个目标函数和一组约束条件，我们需要找到一组满足所有约束条件的01变量值，使得目标函数达到最优（最大或最小）。

证明过程：

1.证明0-1整数规划问题属于NP：

2.证明0-1整数规划问题至少和某个已知的NPC问题一样难：

四、Set packing（Set packing）

问题描述 Set Packing 问题是一个组合优化问题，给定一个集合的集合（通常称为“超集”或“宇宙”U），以及一系列子集 S_1, S_2, …, S_n，其中每个 S_i 都是 U 的子集。Set Packing 问题的目标是找到这些子集的一个子集（称为“packing”），使得 packing 中的任何两个子集都不相交（即它们的交集为空集）。

证明过程： 1.Set Packing 是 NP 问题 给定一个子集集合 S_1, S_2, …, S_n 和一个可能的 packing P（即 P 是 S_1, S_2, …, S_n 的一个子集），验证 P 是否是一个有效的 packing 可以通过检查 P 中任意两个子集 S_i 和 S_j（其中 i ≠ j）的交集是否为空集来完成。这可以在多项式时间内完成，因为子集的数量是有限的，且检查两个集合的交集是否为空集是一个常数时间操作。

2.Set Packing 至少和 3SAT 问题一样难 我们将使用 3SAT 问题的实例来构造一个 Set Packing 问题的实例。 假设我们有一个 3SAT 问题的实例，其中包含 m 个子句和 n 个变量 x_1, x_2, …, x_n。 对于每个变量 x_i，我们创建两个集合 X_i 和 Xbar_i，分别表示 x_i 为真和 x_i 为假的情况。具体来说，如果 x_i 在某个子句中以正文字的形式出现，则将该子句对应的元素添加到 X_i 中；如果 x_i 在某个子句中以负文字的形式出现，则将该子句对应的元素添加到 Xbar_i 中。 对于每个子句 C_j（假设它包含文字 l_1 ∨ l_2 ∨ l_3），我们创建一个集合 C_j，它包含三个元素，分别对应于这三个文字。 宇宙 U 是所有 X_i、Xbar_i 和 C_j 的并集。 Set Packing 问题的目标是找到一个 packing，即找到一个子集集合，使得这个集合中的任何两个子集都不相交。由于每个 C_j 都与三个 X_i 或 Xbar_i 集合相交（对应于子句 C_j 中的三个文字），因此一个有效的 packing 必须包含恰好一个与每个 C_j 相交的 X_i 或 Xbar_i 集合。这对应于为 3SAT 问题中的每个子句选择一个使其为真的文字。 因此，如果 3SAT 问题有一个解（即一个满足所有子句的变量赋值），则 Set Packing 问题也有一个解（即一个有效的 packing）。反之亦然。 归约过程可以在多项式时间内完成，因为我们只需要遍历 3SAT 问题中的每个子句和变量来构造 Set Packing 问题的实例。

五、最小顶点覆盖问题（Vertex cover）

问题描述 最小顶点覆盖问题（Minimum Vert