众所周知，网络流问题可以归结为线性规划问题。然而，在求解网络流问题时，我们需要流始终是整数所以我认为网络流应该简化为整数线性规划。由于ilp是np完全问题，网络流问题也应该是np完全问题。但这与我们所学的相矛盾，因为网络流的运行时间是o（cm）！我错在哪里是因为网络流问题的运行时间是伪多项式时间，就像背包问题（Wn）我现在很困惑！
最佳答案
从技术上讲，你仍然需要证明，还原需要多项式时间，但这是一个比较小的问题。主要的问题是你的减价是错误的。
要证明某个东西是np完全的，您需要做两件事：
表明它是NP形式的
证明它也是np难的。
要使用归约来实现后者，需要将ILP归约为网络流，而不是将网络流归约为ILP减少的目的是证明，如果你能解决给定的问题（在这种情况下，是网络流），你可以在多项式时间内解决ilp（并通过扩展，每个np问题）。通过减少错误的方法，您实际上已经展示了，如果您可以在多项式时间内解ilp，则可以在多项式时间内解网络流（这是真的，但由于网络流在p中，因此没有用）。