Gradually intractable problems and nondeterministic log-space lower bounds
From MaRDI portal
Publication:3700836
DOI10.1007/BF01699467zbMath0578.68039OpenAlexW2010217280MaRDI QIDQ3700836
Publication date: 1985
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01699467
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Simultaneous (poly-time, log-space) lower bounds ⋮ On the complexity of deciding fair termination of probabilistic concurrent finite-state programs ⋮ A multiparameter analysis of domino tiling with an application to concurrent systems ⋮ Communicating processes, scheduling, and the complexity of nontermination ⋮ A multiparameter analysis of the boundedness problem for vector addition systems
Cites Work
- Unnamed Item
- Space-bounded reducibility among combinatorial problems
- Transformational methods and their application to complexity problems
- Techniques for separating space complexity classes
- Relating refined space complexity classes
- On two-way multihead automata
- Some combinatorial game problems require Ω( n k ) time
- Classes of Pebble Games and Complete Problems
- New problems complete for nondeterministic log space
