The Maximum Flow Problem is Log Space Complete for P
The Maximum Flow Problem is Log Space Complete for P
复制标题
最大流问题是 P 的对数空间完整
DOI：
10.1016/0304-3975(82)90092-5
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
J. Staples
中科院分区：
文献类型：
--
作者：
L. Goldschlager;Ralph A. Shaw;J. Staples
研究了最大流问题的空间复杂性。结果表明，该问题是对数空间完全的确定性多项式时间。因此，最大流问题可能没有算法，只需要O（logkn）存储空间的任何constantk。另一个后果是，可能没有快速并行算法的最大流问题。
The space complexity of the maximum flow problem is investigated. It is shown that the problem is log space complete for deterministic polynomial time. Thus the maximum flow problem probably has no algorithm which needs only O(logkn) storage space for any constantk. Another consequence is that there is probably no fast parallel algorithm for the maximum flow problem.