algorithm - 网络流和整数线性规划

Question

我们都知道，网络流的问题可以归结为线性规划。但是，当我们解决网络流量问题时，我们需要流量始终是整数。所以我认为网络流量应该简化为整数线性规划。由于ILP是NP完全的，网络流量问题也应该是NP完全问题。但这与我们所学到的相矛盾，因为网络流的运行时间是 O(Cm)！我哪里错了？是因为网络流问题的运行时间是像背包问题（Wn）这样的伪多项式时间吗？我现在很困惑！

Answer 1

从技术上讲，您仍然必须证明减少需要多项式时间，但这是一个较小的问题。主要问题是您的减少是错误的方法。

为了证明某事是 NP 完全的，你需要做两件事：

1. 证明它在 NP 中
2. 证明它也是 NP 难的。

要使用归约进行后者，您需要将ILP 归约为 network flow，而不是将 network flow 归约为 ILP。减少的重点是表明，如果您可以解决给定的问题（在本例中为网络流），您可以在多项式时间内解决 ILP（以及扩展的每个 NP 问题）。通过减少错误的方法，您实际上已经表明，如果您可以在多项式时间内解决 ILP，您可以在多项式时间内解决网络流（这是正确的，但因为网络流在 P 中，所以没用）。