NP 完全问题到分区问题的减少
NP-Complete problems to Partition Problem reductions
根据维基百科，Partition Problem (PP) 是 NP 完全 (NPC) 问题，现有 伪多项式时间动态规划 (DP ) 解决方案。如果问题是 NPC，则任何 NP 问题都可以在多项式时间内简化为此类问题的实例，即旅行商问题 (TSP) 实例到 PP 实例。现在没有算法，DP 或其他方式，使 TSP 具有比 O(2^n).
更好的绑定
现在，为什么我可以使用 TSP 实例，从中创建 PP 实例，在伪多项式时间内求解 PP 实例并将其缩减？ 减少只花费了我一些多项式。
这里的问题是“伪多项式数量是多少？”对于背包问题，pseudopolynomial-time算法运行时间为O(nW)，其中W为任何物品的最大重量。如果您实际尝试 运行 通过使用当今已知的“标准”减少来减少 TSP（或大多数其他 NP-complete 问题）到背包的细节，您会发现物品的重量是巨大的并且这些问题的输入量通常呈指数级增长。例如，从集合包装到背包的典型简化是通过构建重量约为 2n 的项目来实现的，其中 n 是所有集合中不同项目的数量。这使得首先使用此归约然后应用背包的运行时间为 O(n · 2n)，这不是伪多项式时间。
根据维基百科，Partition Problem (PP) 是 NP 完全 (NPC) 问题，现有 伪多项式时间动态规划 (DP ) 解决方案。如果问题是 NPC，则任何 NP 问题都可以在多项式时间内简化为此类问题的实例，即旅行商问题 (TSP) 实例到 PP 实例。现在没有算法，DP 或其他方式，使 TSP 具有比 O(2^n).
现在，为什么我可以使用 TSP 实例，从中创建 PP 实例，在伪多项式时间内求解 PP 实例并将其缩减？ 减少只花费了我一些多项式。
这里的问题是“伪多项式数量是多少？”对于背包问题，pseudopolynomial-time算法运行时间为O(nW)，其中W为任何物品的最大重量。如果您实际尝试 运行 通过使用当今已知的“标准”减少来减少 TSP（或大多数其他 NP-complete 问题）到背包的细节，您会发现物品的重量是巨大的并且这些问题的输入量通常呈指数级增长。例如，从集合包装到背包的典型简化是通过构建重量约为 2n 的项目来实现的，其中 n 是所有集合中不同项目的数量。这使得首先使用此归约然后应用背包的运行时间为 O(n · 2n)，这不是伪多项式时间。