Complete problems for space bounded subclasses of NP
From MaRDI portal
Publication:1064779
DOI10.1007/BF00288774zbMATH Open0576.68031OpenAlexW2056508159MaRDI QIDQ1064779FDOQ1064779
Authors: W. Michael Evangelist, I. H. Sudborough, Moon Jung Chung
Publication date: 1985
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00288774
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relationships between nondeterministic and deterministic tape complexities
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The complexity of satisfiability problems
- Some simplified NP-complete graph problems
- The NP-completeness of the bandwidth minimization problem
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Complexity Results for Bandwidth Minimization
- Space-bounded reducibility among combinatorial problems
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Bandwidth constraints on problems complete for polynomial time
- Bandwidth and pebbling
- On the complexity of some problems concerning the use of procedures. II
- Bandwidth contrained NP-complete problems
Cited In (12)
- On Some $\mathcal{NP}$ -complete SEFE Problems
- The Null Space Problem I. Complexity
- Complete problems for monotone NP
- Sublinear P system solutions to NP-complete problems
- Title not available (Why is that?)
- Bandwidth constraints on problems complete for polynomial time
- Title not available (Why is that?)
- Some remarks on subclass containment problems for several classes of dpda's
- Title not available (Why is that?)
- On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Bandwidth contrained NP-complete problems
This page was built for publication: Complete problems for space bounded subclasses of NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1064779)