The maximum flow problem is log space complete for P

Theoretical Computer SciencePublished 1 October 1982

Leslie M. Goldschlager, Ralph A. Shaw, John Staples

DOI10.1016/0304-3975(82)90092-5

Source URL

Citations133

SJR quartileQ2

SJR score0.49

SNIP0.94

TL;DR

It is shown that the problem is log space complete for deterministic polynomial time, so the maximum flow problem probably has no algorithm which needs only O(logk n) storage space for any constant k.

Abstract

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(logk n) storage space for any constant k. Another consequence is that there is probably no fast parallel algorithm for the maximum flow problem.

Keywords

Computer Science

Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation

10,827 Citations1981

Graph Algorithms

1,284 Citations1979Shimon Even

A thoroughly revised second edition of Shimon Even's Graph Algorithms, with a foreword by Richard M. Karp and notes by Andrew V Goldberg, explains algorithms in a formal but simple language with a direct and intuitive presentation.

ACM SIGACT NewsThe circuit value problem is log space complete for <i>P</i>

305 Citations1975Richard E. Ladner

The set P is the set of problems computable in polynomial_ time and the circuit value problem is CV, which is well known that a T(n) time bounded Turing machine can be simulate on n bits by a combinational circuit with 0(T-(n) gates.

Theoretical Computer ScienceComplete problems for deterministic polynomial time

279 Citations1976Neil D. Jones, William T. Laaser

ACM SIGACT NewsThe monotone and planar circuit value problems are log space complete for P

216 Citations1977Leslie M. Goldschlager

It is shown that Ladner's simulation of Turing mac]hines by boolean circuits seems to require an "adequate" set of gates, such as AND and NOT, but the same simulation is possible with monotone circuits using AND and OR gates only.

Journal of Computer and System SciencesAn observation on time-storage trade off

202 Citations1974Stephen Cook

Complexity of finitely presented algebras

158 Citations1977Dexter Kozen

The schema satisfiability problem and schema validity problem are shown to be ≤m m log-complete for NP and co-NP, respectively, and the problem of isomorphism of finitely presented algebras is shown to to be polynomial time many-one equivalent to the issue of graph isomorphicism.

A unified approach to models of synchronous parallel machines

127 Citations1978Leslie M. Goldschlager

Strong evidence of the general applicability of the parallel computation thesis is given and strong evidence of its truth is given in this paper by introducing the notion of “conglomerates” - a very large class of parallel machines, including all those which could feasibly be built.

View PDF

Acta InformaticaHierarchies of complete problems

41 Citations1976Zvi Galil

A new concept—a Hierarchy of Complete Problems is defined and several hierarchies in various domains such as graph theory, automata theory, theorem proving and games are established.

Acta Informatica?-productions in context-free grammars

15 Citations1981Leslie M. Goldschlager

It is shown that the removal of ɛ-productions from a context-free grammar can probably not be achieved with small storage space, which explains the apparent discrepancy between two different results in the literature on the membership problem.