一些 NP 难的问题也是固定参数可处理的，或 FPT。如果有一种算法可以在时间 f(k) · |x| 中解决问题，维基百科将问题描述为可处理的固定参数 O(1)。
这是什么意思？为什么这个概念有用？
问问题
10307 次
1 回答
64
首先，在 P ≠ NP 的假设下，对于任何 NP-hard 问题都没有多项式时间的精确算法。虽然我们不知道 P = NP 还是 P ≠ NP，但我们没有任何多项式时间算法来解决任何 NP 难题。
固定参数可处理性背后的想法是处理一个 NP 难题，我们不知道任何多项式时间算法，并尝试将复杂性分成两部分 - 有些部分完全取决于输入，以及一些取决于问题的“参数”的部分。
例如，考虑0/1 背包问题。在这个问题中，你会得到一个包含 n 个具有相关权重和值的对象的列表，以及允许你携带的最大重量 W。问题是确定您可以携带的最大价值量。这个问题是 NP 难的，这意味着没有多项式时间算法可以解决它。蛮力方法将花费大约 O(2 n) 通过考虑项目的所有可能子集，这对于大 n 来说非常慢。但是，可以在 O(nW) 时间内解决这个问题，其中 n 是元素的数量，W 是您可以携带的重量。如果您查看运行时 O(nW)，您会注意到它分为两部分：元素数量呈线性的分量（n 部分）和权重呈线性的分量（W 部分）。如果 W 是任何固定常数，那么该算法的运行时间将是 O(n)，这是线性时间，即使问题通常是 NP-hard。这意味着，如果我们将 W 视为问题的某个可调“参数”，对于该参数的任何固定值，问题最终都会在多项式时间内运行（这在复杂性理论的意义上是“易处理的”。）
作为另一个例子，考虑在图中找到长而简单的路径的问题。这个问题也是 NP 难的，在图中寻找长度为 k 的简单路径的简单算法需要时间 O(n! / (n - k)!)，对于大 k 最终是超指数的。但是，使用颜色编码技术，可以在 O((2e) k n 3 log n)时间内解决这个问题，其中 k 是要查找的路径的长度，n 是输入中的节点数图形。请注意，此运行时还具有两个“组件”：一个组件是输入图中节点数的多项式（n 3 log n 部分）和一个以 k 为指数的组件（（2e）k部分）。这意味着对于任何固定的 k 值，都有一个多项式时间算法可以在图中找到长度为 k 的路径；运行时间将为 O(n 3 log n)。
在这两种情况下，我们可以解决一个我们有指数时间解决方案（或更糟）的问题，并找到一个新的解决方案，它的运行时间是某个多项式的 n 乘以某个额外“参数”的某个看起来很疯狂的函数。在背包问题的情况下，该参数是我们可以携带的最大重量；在查找长路径的情况下，参数是要查找的路径的长度。一般来说，如果有一些算法可以解决问题，该问题用两个量定义：n，输入的大小，k，一些“参数”，其中运行时间为
O(p(n) · f(k))
其中 p(n) 是某个多项式函数，而 f(k) 是 k 中的任意函数。直观地说，这意味着问题的复杂性随 n 呈多项式缩放（这意味着随着问题大小的增加，运行时会很好地缩放），但可以随参数 k 任意缩放。这将问题的“固有难度”分离出来，使得问题的“困难部分”归咎于参数 k，而问题的“简单部分”归咎于输入的大小。
一旦你有一个看起来像 O(p(n) · f(k)) 的运行时，我们立即得到多项式时间算法来解决任何固定 k 的问题。具体来说，如果 k 是固定的，那么 f(k) 是某个常数，所以 O(p(n) · f(k)) 就是 O(p(n))。这是一个多项式时间算法。因此，如果我们“修复”参数，我们就会得到一些“易于处理”的算法来解决问题。这就是固定参数易处理一词的由来。
（注：维基百科对固定参数易处理性的定义说该算法应该有运行时间 f(k) · |x| O(1)。这里，|x| 是指输入的大小，我称之为 n这里。这意味着维基百科的定义与说运行时是 f(k) · n O(1)相同。正如前面的答案中提到的，n O(1)表示“n 中的某个多项式”，所以这个定义最终等同于我在这里给出的定义）。
固定参数的可处理性对问题具有巨大的实际意义。遇到 NP 难的问题是很常见的。如果您发现问题是固定参数可处理且参数较低，则使用固定参数可处理算法比使用普通的蛮力算法更有效。例如，上面用于在图中查找长路径的颜色编码示例已在计算生物学中用于查找酵母细胞中的测序路径取得了巨大成功，并且经常使用 0/1 背包解决方案，因为 W 的常见值是足够低以使其实用。
希望这可以帮助！
于 2013-10-28T19:57:37.130 回答