Gradually intractable problems and nondeterministic log-space lower bounds
From MaRDI portal
Recommendations
Cites work
- Classes of Pebble Games and Complete Problems
- scientific article; zbMATH DE number 3557247 (Why is no real title available?)
- New problems complete for nondeterministic log space
- On two-way multihead automata
- Relating refined space complexity classes
- Some combinatorial game problems require Ω( n k ) time
- Space-bounded reducibility among combinatorial problems
- Techniques for separating space complexity classes
- Transformational methods and their application to complexity problems
Cited in
(8)- 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
- A multiparameter analysis of the boundedness problem for vector addition systems
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Communicating processes, scheduling, and the complexity of nontermination
- scientific article; zbMATH DE number 4049049 (Why is no real title available?)
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
This page was built for publication: Gradually intractable problems and nondeterministic log-space lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3700836)
