决策问题与非是或否的“真实”问题

Question

我在很多地方读到有些问题很难近似（这是 NP难 近似 他们）。但近似不是决策问题：答案是一个实数，而不是“是”或“否”。此外，对于每个所需的近似因子，都有许多正确的答案和许多错误的答案，并且这会随着所需的近似因子而变化！

那么怎么能说这个问题是NP-hard问题呢？

（受到第二个项目符号的启发 计算有向图中两个节点之间的简单路径的数量有多难？)

Answer 1

正如您所说，没有做出决定，因此需要新的复杂性类别和新的减少类型来得出合适的定义 NP硬度 为了 优化问题.

一种方法是创建两个新类 非营利组织 和 采购订单 包含 优化问题 他们当然模仿课堂 NP 和 磷 对于决策问题。还需要新的削减。然后我们可以重新创建一个版本 NP硬度 对于优化问题，与决策问题的成功类似。但首先我们必须同意什么是 优化问题 是。

定义：设 $O=(X,L,f,opt)$ 为 优化问题. 。$X$ 是一组 输入 或者 实例 适合编码为字符串。$L$ 是一个函数，它将每个实例 $x\in X$ 映射到一组字符串， 可行的解决方案 实例$x$。它是一个集合，因为优化问题有很多解决方案。因此我们有一个 目标函数 $f$ 告诉我们每对 $(x, y)$ $y\in L(x)$ 实例及其解 成本 或者 价值. 。$opt$ 告诉我们是最大化还是最小化。

这使我们能够定义什么是 最优解 是：设 $y_{opt}\in L(x)$ 为 最优解 实例 $x\in X$ 的优化问题 $O=(X,L,f,opt)$ 且 $$f(x,y_{opt})=opt\{f(x,y') \mid y'\in L(x)\}.$$ 最优解通常用 $y^*$ 表示。

现在我们可以定义类了 非营利组织: ：令 $NPO$ 为所有优化问题 $O=(X,L,f,opt)$ 的集合，其中：

1. $X\in P$
2. 对于所有实例 $x\in X$ 和所有可行解 $y\in L(x)$，存在一个多项式 $p$，其中 $|y|\le p(|x|)$。此外，还有一种确定性算法可以在多项式时间内决定 $y\in L(x)$ 是否成立。
3. $f$ 可以在多项式时间内求值。

其背后的直觉是：

1. 我们可以有效地验证 $x$ 是否确实是优化问题的有效实例。
2. 可行解的大小受输入大小的多项式限制，我们可以有效地验证 $y\in L(x)$ 是否是实例 $x$ 的可行解。
3. 解 $y\in L(x)$ 的值可以有效地确定。

这反映了 $NP$ 的定义方式，现在为 采购订单: ：令 $PO$ 为 $NPO$ 中可以通过确定性算法在多项式时间内解决的所有问题的集合。

现在我们可以定义我们想要调用的内容 近似算法: ：一个 近似算法 优化问题 $O=(X,L,f,opt)$ 是一种算法，用于计算实例 $x\in X$ 的可行解 $y\in L(x)$。

笔记：我们不要求 最佳的 解决方案我们只有一个 可行的 一。

现在我们有两种类型的错误：这 绝对误差 优化问题 $O=(X,L,f,opt)$ 的实例 $x\in X$ 的可行解 $y\in L(x)$ 是 $|f(x,y)- f(x,y^*)|$。

如果算法 $A$ 为每个实例 $x\in X$ 计算一个绝对误差有界的可行解，则我们将优化问题 $O$ 的近似算法 $A$ 的绝对误差称为以 $k$ 为界的由$k$。

例子：根据 Vizing 定理 色彩指数 图的颜色数（使用最少颜色的边缘着色中的颜色数）是 $\Delta$ 或 $\Delta+1$，其中 $\Delta$ 是最大节点度。根据定理的证明，可以设计一种近似算法来计算具有 $\Delta+1$ 颜色的边缘着色。因此，我们有一个针对 $\mathsf{Minimum-EdgeColoring}$ 问题的近似算法，其中绝对误差以 $1$ 为界。

这个例子是一个例外，小的绝对误差很少见，因此我们定义 相对误差 优化问题$O=(X,L,f,opt)$实例$x$上的近似算法$A$的$\epsilon_A(x)$，其中$f(x,y)>0$所有 $x\in X$ 和 $y\in L(x)$ 为

$$\epsilon_A(x):=\begin{情况}0&f(x,A(x))=f(x,y^*)\\\frac{|f(x,A(x))-f( x,y^*)|}{\max\{f(x,A(x)),f(x,y^*)\}}&f(x,A(x)) e f(x,y) ^*)\end{案例}$$

其中 $A(x)=y\in L(x)$ 是由近似算法 $A$ 计算的可行解。

我们现在可以将优化问题 $O=(X,L,f,opt)$ 的近似算法 $A$ 定义为 $\delta$-近似算法 对于$ o $，如果相对错误$ epsilon_a（x）$由$ delta ge 0 $限制在x $中的每个实例$ x ，那么$ epsilon_a（x） le delta qquad qquad qquad forall x inx。$$

在相对误差定义的分母中选择 $\max\{f(x,A(x)),f(x,y^*)\}$ 是为了使最大化和最小化的定义对称。相对误差 $\epsilon_A(x)\in[0,1]$ 的值。在最大化问题的情况下，解的值永远不会小于 $(1-\epsilon_A(x))\cdot f(x,y^*)$ 并且永远不会大于 $1/(1-\epsilon_A(x) )\cdot f(x,y^*)$ 用于最小化问题。

现在，如果 $O$ 有一个在多项式时间内运行的 $\delta$-近似算法 $A$，我们就可以调用优化问题 $\delta$-approximable。

我们不想查看每个实例 $x$ 的错误，我们只查看最坏的情况。因此我们定义$\epsilon_A(n)$， 最大相对误差 优化问题$ o $ $ o $的近似值 - algorithm $ a $ a $

$|x|$ 应该在哪里 尺寸 实例的。

例子：通过将匹配中的所有事件节点添加到顶点覆盖，可以将图中的最大匹配转换为最小节点覆盖 $C$。因此 $1/2\cdot |C|$ 边缘被覆盖。由于每个顶点覆盖（包括最优顶点覆盖）必须具有每个覆盖边的节点之一，否则可以改进，我们有 $1/2\cdot |C|\cdot f(x,y^*)$。因此，$$ frac {| c | -f（x，y^*）} {| c |} le frac {1} {2} $$因此，最大匹配的贪婪算法是$ 1/ 2 $ -Approximatio-Algorithm for $ Mathsf {minimal-vertexcover} $。因此 $\mathsf{Minimal-VertexCover}$ 是 $1/2$ 近似的。

不幸的是，相对误差并不总是近似质量的最佳概念，如以下示例所示：

例子：一个简单的贪心算法可以近似$\mathsf{Minimum-SetCover}$。分析表明 $$\frac{|C|}{|C^*|}\le H_n\le 1+\ln(n)$$ ，因此 $\mathsf{Minimum-SetCover}$ 将是 $\frac {\ln(n)}{1+\ln(n)}$-近似。

如果相对误差接近 $1$，则以下定义​​是有利的。

设 $O=(X,L,f,opt)$ 是一个优化问题，对于所有 $x\in X$ 和 $y\in L(x)$ 和 $，$f(x, y)>0$ A$ 是 $O$ 的近似算法。这 近似比 可行解决方案的$ r_a（x）$ （x））= f（x，y^*） x max left { frac {f（x，a（x））} {f（x，x，y^*）}， frac {f（f） x，y^*）} {f（x，a（x））} right }＆f（x，a（x）） ne f（x，y^*） end {cases} $$

和之前一样，如果每个输入 $ 的近似比 $r_A(x)$ 以 $r\ge1$ 为界，我们将优化问题 $O$ 的近似算法 $A$ 称为 $r$ 近似算法x\in X$。$$ r_a（x） le r $$，如果我们有一个$ r $ - approximation-algorithm $ a $用于优化问题$ o $ $ o $，则$ o $称为 $r$-近似. 。同样，我们只关心最坏的情况并定义 最大近似比 $ r_a（n）$ to为$$ r_a（n）= sup {r_a（x） mid | x | x | le n }。$$，近似值大于$ 1 $ suboptimal solutions。因此，更好的解决方案具有更小的比率。对于$\mathsf{Minimum-SetCover}$，我们现在可以写出它是$(1+\ln(n))$-可近似的。在 $\mathsf{Minimum-VertexCover}$ 的情况下，我们从前面的示例中知道它是 $2$ 近似的。相对误差和近似比之间有简单的关系：$$r_A(x)=\frac{1}{1-\epsilon_A(x)}\qquad \epsilon_A(x)=1-\frac{1}{r_A(x)}.$$

对于与最佳值 $\epsilon<1/2$ 和 $r<2$ 的小偏差，相对误差优于近似比，这显示了其对于大偏差 $\epsilon\ge 1/2$ 和 $r 的优势\ge 2$。

$\alpha$-可近似的两个版本不重叠，因为一个版本始终为 $\alpha\le 1$，另一个版本始终为 $\alpha\ge 1$。$\alpha=1$ 的情况没有问题，因为这只能通过产生精确解的算法来实现，因此不需要被视为近似算法。

另类经常出现 亚太经合组织. 。它被定义为来自 $NPO$ 的所有优化问题 $O$ 的集合，这些问题具有 $r$ 近似算法，其中 $r\ge1$ 在多项式时间内运行。

我们快结束了。我们想复制成功的想法 减少 和 完整性 来自复杂性理论。观察结果是，优化问题的许多 NP 难决策变体可以相互简化，而它们的优化变体在近似性方面具有不同的属性。这是由于 NP 完备性约简中使用了多项式时间卡普约简，它不保留目标函数。即使保留目标函数，多项式时间卡普缩减也可能会改变解决方案的质量。

我们需要的是更强的归约版本，它不仅将优化问题 $O_1$ 的实例映射到 $O_2$ 的实例，而且还将 $O_2$ 的良好解决方案映射回 $O_1$ 的良好解决方案。

因此我们定义 近似保持约简 对于来自 $NPO$ 的两个优化问题 $O_1=(X_1,L_1,f_1,opt_1)$ 和 $O_2=(X_2,L_2,f_2,opt_2)$。如果有两个函数 $g$ 和 $h$ 以及一个常量 $c$，我们称 $O_1$ $AP$ 可简化为 $O_2$，写为 $O_1\le_{AP} O_2$：

1. $g(x_1, r)\in X_2$ 对于所有 $x_1\in X_1$ 和有理数 $r>1$
2. $L_2(g(x, r_1)) e\emptyset$ 如果 $L_1(x_1) e\emptyset$ 对于所有 $x_1\in X_1$ 且有理数 $r>1$
3. $h(x_1, y_2, r)\in L_1(x_1)$ 对于所有 $x_1\in X_1$ 和有理数 $r>1$ 以及对于所有 $y_2\in L_2(g(x_1,r))$
4. 对于固定的 $r$，函数 $g$ 和 $h$ 都可以通过两种算法在其输入长度的多项式时间内计算。
5. 我们有 $$f_2(g(x_1,r),y_2)\le r ightarrow f_1(x_1,h(x_1,y_2,r))\le 1+c\cdot(r-1) $$ 对于所有 $ x_1\in X_1$ 和有理 $r>1$ 以及所有 $y_2\in L_2(g(x_1,r))$

在此定义中，$g$ 和 $h$ 取决于解决方案 $r$ 的质量。因此，对于不同的质量，功能可能不同。这种通用性并不总是需要的，我们只需使用 $g(x_1)$ 和 $h(x_1, y_2)$ 即可。

现在我们有了减少优化问题的概念，我们终于可以转移我们从复杂性理论中知道的许多东西。例如，如果我们知道 $O_2\in APX$ 并且我们显示 $O_1\le_{AP} O_2$，那么 $O_1\in APX$ 也是如此。

最后我们可以定义优化问题的 $\mathcal{C}$-hard 和 $\mathcal{C}$-complete 的含义：

设 $O$ 是 $NPO$ 中的优化问题，$\mathcal{C}$ 是 $NPO$ 中的一类优化问题，则调用 $O$ $\mathcal{C}$-困难 相对于 $\le_{AP}$ 如果对于所有 $O'\in\mathcal{C}$ $O'\le_{AP} O$ 成立。

因此我们再一次有了一个概念 最难的 课堂上的问题。不足为奇的是 $\mathcal{C}$-困难 如果问题是 $\mathcal{C}$ 的元素，则相对于 $\le_{AP}$ 而言，该问题被称为 $\mathcal{C}$ 完全。

因此，我们现在可以讨论 $NPO$-完整性和 $APX$-完整性等。当然，我们现在被要求展示第一个 $NPO$ 完整问题，该问题取代了 $\mathsf{SAT}$ 的角色。几乎很自然地，$\mathsf{加权可满足性}$ 可以被证明是 $NPO$ 完全的。借助 PCP 定理，我们甚至可以证明 $\mathsf{Maximum-3SAT}$ 是 $APX$ 完备的。

Answer 2

通常显示的是问题的“差距”版本的NP硬度。例如，假设您想证明很难将设置覆盖范围近似于2倍。

您定义了以下设置封面的“承诺”实例，我们将调用2-gap-set-cover：

修复一些数字$ ell $。 2间隙集合包含的所有设置覆盖实例，其中最佳设置盖的大小是：

• 最多$ ell $
• 至少$ 2 ell $

假设我们表明，确定问题中的两种情况中的哪种问题是NP完成的问题。然后，我们表明，近似于2倍的近似值为NP- hard，因为我们可以使用这种算法来区分这两种情况。

Answer 3

现有的两个答案非常有用，但我认为他们中的任何一个都没有真正回答这个问题，即“当NP是一类决策问题时，都不是决策问题的问题如何？”

答案是记住NP-HARD的含义。如果可以将NP中的每个问题减少到$ L $，则在某种降低的情况下，$ L $ $ L $是NP-HARD。 （如果它是NP-HARD和NP，则$ L $是NP的完整。不在NP中。 NP硬度不需要NP的成员资格，但确实需要正确的减少概念。

一些例子。

1. 在多项式时间内减少的情况下，任何Nexptime-Complete问题$ L $都是NP-HARD。 NP中的任何问题都在Nexptime中，因此从定义上可以还原为$ L $。到层次定理时，$ l $不能在NP中，因此$ L $不是NP组件。
2. #SAT是计算CNF公式满足分配数量的问题。显然，它不在NP中，因为正如您所观察到的那样，NP是一类决策问题，#SAT不是其中之一。但是，#sat在多项式的图灵降低下是NP-HARD，因为我们可以减少SAT。鉴于SAT实例，我们问有多少个满足的作业：如果至少有一个，我们说“令人满意”；否则，“不满意”。
3. 让大约是计算一个数字的问题，该数字不超过到CNF公式$ varphi $的满足分配数量的十倍。只是为了烦恼，假设您允许您四舍五入，因此，如果$ varphi $具有三个令人满意的作业，则允许算法思考“ 0.3”并将其舍入到零。这是多项式时间的图灵降低，因为我们仍然可以减少SAT。给定CNF公式$ varphi $，要求询问$ varphi'= varphi wedge（z_1 vee dots dots vee z_ {10}）$的满足分配数量，其中$ z_i $是新的变量。 $ varphi'$在当$ varphi $ is的情况下，但是$ varphi'$可以保证具有超过1,000个令人满意的作业（如果有任何），则可以满足$ varphi' $。因此，$ varphi $是可以满足的，并且只有当大约算法说$ varphi'$至少具有100个令人满意的作业。