Organisedproblems

约 2696 个字预计阅读时间 13 分钟

Satisfiability (SAT problem)¶

SAT 问题的目标是：给定一个布尔公式，判断是否存在一种变量赋值使得公式为真。

因此 SAT 问题是 NP 问题，是 NPC 问题，也是 NPH 问题。

SAT 是第一个被证明为 NP-complete 的问题（由 Stephen Cook 在 1971 年提出的 Cook 定理）。

根据 Cook 定理，任何 NP 问题都可以通过多项式时间归约（polynomial-time reduction）转化为 SAT 问题。因此，SAT 是 NP 中的“最难”问题之一，所有其他 NP 问题都可以通过多项式时间归约到 SAT。

2-SAT 问题¶

然而对于 2-SAT 问题来说是 P 问题。

我们可以通过以下方式证明：

构造蕴含图：

对于每一个形如 \(x_i \cup x_j\) 的子句，我们添加两条有向边：

\[\neg x_i \rightarrow x_j\]

\[\neg x_j \rightarrow x_i\]

强连通分量分解：

使用 Kosaraju 或 Tarjan 算法将构造的蕴含图分解为强连通分量（SCC）。

检测矛盾：

检查是否有任何一对互补的变量 \(x_i\) 和 \(\neg x_i\) 属于同一个强连通分量。如果有这样的情况，那么公式是不可满足的，因为这意味着 \(x_i\) 必须同时为真和假，这是不可能的。

拓扑排序与赋值：

如果没有矛盾，我们可以根据强连通分量的拓扑排序来确定变量的赋值。具体来说，从后向前遍历 SCC，一旦遇到一个尚未赋值的变量 \(x_i\) ，就将其设为真，并根据蕴含关系更新其他变量的值。

复杂度分析：

构建蕴含图：需要线性时间 \(O(m)\) ，其中 \(m\) 是子句的数量。
强连通分量分解：Kosaraju 或 Tarjan 算法的时间复杂度是 \(O(n+m)\) ，其中 \(n\) 是变量的数量，\(m\) 是子句的数量。
检测矛盾及赋值：这部分操作也是线性的。

因此，整个算法的时间复杂度是 \(O(n+m)\) ，这是一个多项式时间复杂度。

Clique Problem（团问题）¶

最大团问题（Maximum Clique Problem）：给定一个无向图，找出具有最多顶点的完全子图。这是一个优化问题。
团判定问题（Clique Decision Problem）：给定一个无向图和一个整数 k ，确定是否存在一个大小至少为 k 的完全子图。这是一个决策问题。

Clique 问题的复杂性¶

Clique 问题是 NP 完全问题。这意味着：

NP：对于给定的解（即一组顶点），可以在多项式时间内验证这些顶点是否构成一个大小至少为 k 的团。
NP 完全：任何 NP 问题都可以在多项式时间内转化为团问题，并且如果能找到一个解决团问题的多项式时间算法，则可以解决所有的 NP 问题。

具体证明移步课程笔记。

Tautology Problem¶

问题描述：给定一个布尔公式 \(\phi\) ，判断它是否对所有可能的变量赋值都为真（即 \(\phi\) 是恒真的）。

Tautology Problem 是 NPH 问题，大概率不是 NP 问题，所以大概率不是 NPC 问题。

为什么说大概率不是 NP 问题呢

因为尚未有严格的数学证明来证明无法在多项式时间内验证。(我个人的理解是或许存在某些值是相互依存的式子会相互影响之类的事情)

因此无法直接确定 Tautology Problem 是否是 NP 问题。

TSP, Traveling Salesman Problem（旅行商问题）¶

旅行商问题¶

核心是：

给定一组城市和城市之间的距离（或成本），一个旅行商需要从起始城市出发，访问每个城市一次并返回起始城市。
目标：找到总旅行距离（或成本）最小的路径。

TSP 问题是 NPH 问题，但不是 NP 问题，因此不是 NPC 问题。

除非 NP = P ，否则对于任意 \(k \ge 1\) ， TSP 不存在 k - 近似算法。

然而，现实中的TSP 边的权重（也就是旅行商在两点之间通行的距离）应当满足下述三角不等式：

\[w(u,v) \le w(u,x) + w(x,v)\]

但是在添加度量空间的条件后，旅行商问题存在如下 2-近似算法：首先求出图 G 的最小生成树 T，然后在 T 上按深度优先搜索（先序遍历）的顶点遍历顺序得到一条哈密顿回路，其权重不超过最小生成树的权重的两倍。

TSP 的优化版本¶

同样的 TSP 问题的优化版本是：

找到经过所有城市的最短路径，但不需要回到起点，即构成一个哈密顿路径（Hamiltonian Path）。

TSP 问题的优化版本也是 NPH 问题，但同样不是 NP 问题，因此也不是 NPC 问题。

又一版本¶

给定一个完全图 G = (V, E) 和一个整数 k，判断是否存在一个哈密顿回路，使得其长度不超过 k。

此时属于 NP 问题，因此此时这个问题是 NPH 问题，也是 NPC 问题。

0-1 背包问题¶

在 0-1 背包问题中，有以下条件：

输入： 1. \(n\) 个物品，每个物品 \(i\) 有一个重量 \(w_i\) 和价值 \(v_i\) 。 2. 一个背包，最大承重为 \(W\) 。
目标：从这 \(n\) 个物品中选择若干物品，使得总重量不超过 \(W\) ，并且总价值最大化。

限制条件：¶

每个物品只能选择一次（0 或 1），因此称为 0-1 背包问题。

原始的 0-1 背包问题是 NPC 问题，但不属于多项式时间内可以求解的问题，可以从两方面证明。

（1）状态空间的规模

原问题中，背包容量 \(W\) 可以是任意正整数，且没有对物品重量 \(w_i\) 的限制。
动态规划的时间复杂度为 \(O(nW)\) ，其中 \(W\) 是背包容量。
如果 \(W\) 非多项式有界（例如 \(W = 2^n\) ），则动态规划的运行时间会呈指数增长。

（2）输入大小对计算的影响

在计算复杂性中，问题的难度与输入大小密切相关。输入的大小 \(|I|\)通常按二进制编码计算：
\(|I| = O(n + \log W)\) ，其中 \(n\) 是物品数量，\(\log W\) 是背包容量 \(W\) 的编码长度。
动态规划需要的时间是 \(O(nW)\) ，而非 \(O(n \log W)\) 。当 \(W\) 很大时，计算时间呈现指数增长。也即无法保证需要的时间是输入规模的多项式时间算法内解决。

Makespan Scheduling Problem（最小化工时调度问题）¶

在最小化工时调度问题中：

输入：有 \(n\) 个任务，每个任务 \(i\) 的处理时间为 \(p_i\) ，以及 \(m\) 台并行机器。
目标：将 \(n\) 个任务分配到 \(m\) 台机器上，使得所有机器的最大完成时间（即 工时 makespan）最小。

最小化工时调度问题属于 NPH 问题。它的决策版本(即，是否存在一个调度方案使得最大完工时间不超过某个给定值)是 NPC 的。

`Graham` 算法¶

而当我们运用贪心算法(对每个作业进行调度的时候，我们选择当前工作量最小的机器进行调度)时，可以得到这样的算法近似比为 \(2-\frac{1}{m}\)

而如果先进行排序，再用该算法可以得到近似比为 \(\frac{4}{3} - \frac{1}{3m}\)

装箱问题¶

一维装箱问题：¶

给定若干个带有尺寸的物品，要求将所有物品放入容量给定的箱子中，使得每个箱子中的物品尺寸之和不超过箱子容量并使所用的箱子数目最少。

决策版本 : 给定若干个物品，判断它们是否可由 k 个箱子装下是 NPC 的问题。

优化版本 : 寻找最少数量的箱子来容纳所有的物品是 NPH 的问题。

Note

除非 P = NP，否则装箱算法不存在多项式算法有小于 \(\frac{3}{2}\) 的绝对近似比。

不会存在 “BF(best fit) 总比 FF(first fit) 好” 或者 “FF 总比 BF” 好的结论。

二维装箱问题：¶

我们有两个贪心策略，其一是根据这里的单位重量的价值（即 PPT 上的 profit density），其二是直接贪心选择最大价值的物品，我们运行两个算法选择最优解，我们可以证明，这样结合后的近似比为 2。

我们给定我们想要达到的近似比率 \(\varepsilon\)（为了分析方便，我们假设 \(\frac{1}{\varepsilon}\) 是整数，如果不是整数也可以向下找一个满足条件的数替代），令放缩比例 \(b = \frac{\varepsilon v_{max}}{n}\)
我们将所有价值放缩为 \(\lceil \frac{v_i}{b}\rceil\) ，然后运行动态规划算法得到最优解 v；
然后将所有价值放大为 \(v_i^′ = \lceil \frac{v_i}{b}b \rceil\) ，此时最优解为 bv，然后 bv 就是我们的近似最优解了。

上述算法是 0 − 1 背包问题的一个 FPTAS。

The K-center Problem（聚类问题）¶

这是一个 NPC 问题，可以通过适当构造从顶点覆盖问题或其他相关 NP 完全问题到 K-center 问题的实例。

Greedy-2r 算法在给定最优解 \(r(C^*)\) 的情况下是一个 2-近似算法。

Greedy-Kcenter 算法是一个 2-近似算法。

除非 NP = P ，否则对于 \((\alpha < 2)\) 不存在 \(\alpha\) - 近似算法。

Vertex Cover Problem（顶点覆盖问题）¶

该问题的目标是在给定的无向图中找到最小数量的顶点，使得这些顶点能够“覆盖”所有的边。

换句话说，所选顶点集应该包含每条边的至少一个端点。

顶点覆盖问题是 NPC 问题。

一个简单的贪心算法（记为算法 A）：任意一条边 (u, v)，然后将 u 和 v 同时加入到 C 中，然后把 u和 v 所在的所有边全部移除，下一轮继续在剩下的边中随机选择一条重复上述操作，直到所有的边都被删除为止。

上述顶点覆盖问题的贪心算法 A 是一个 2-近似算法。

Max-Cut Problem(最大割问题)¶

它涉及到在一个给定的无向图中，将顶点集划分为两个子集，使得跨越这两个子集之间的边的数量最大化。

最大割问题是 NPC 问题。

设 (A, B) 是局部搜索算法(利用 State_flipping 算法)得出的一个局部最优解，\((A^*, B^* )\) 是最优解，则

\[\frac{w(A,B)}{w(A^*,B^*)} \ge \frac{1}{2}\]

除非 NP = P ，否则对于 \((\alpha \le \frac{17}{16})\) 不存在 \(\alpha\) - 近似算法。