Linear programming is log-space hard for P
From MaRDI portal
Publication:1255780
DOI10.1016/0020-0190(79)90152-2zbMath0402.68042OpenAlexW2090133546MaRDI QIDQ1255780
Steven P. Reiss, Richard J. Lipton, David P. Dobkin
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90152-2
Related Items
An introduction to parallelism in combinatorial optimization, The parallel complexity of deadlock detection, On renamable Horn and generalized Horn functions, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Parallel search algorithms in global optimization, Parallel approximation algorithms for bin packing, On the complexity of scheduling unrelated parallel machines with limited preemptions, Various approaches to multiobjective linear programming problems with interval costs and interval weights, \(\varepsilon\)-productions in context-free grammars, Two complexity results on \(c\)-optimality in experimental design, Classifying the computational complexity of problems, The maximum flow problem is log space complete for P, An appraisal of computational complexity for operations researchers, Expressing combinatorial optimization problems by linear programs, A canonical form for generalized linear constraints, Learning in parallel, The complexity of linear programming, The complexity of linear programming, On the parallel approximability of a subclass of quadratic programming., Gainfree Leontief substitution flow problems, Approximating linear programming is log-space complete for P, Prediction-preserving reducibility, Polynomial size linear programs for problems in \textsc{P}, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, Depth-first search is inherently sequential, Algorithms and complexity analysis for some flow problems
Cites Work
