Complete problems for space bounded subclasses of NP

DOI10.1007/BF00288774zbMath0576.68031OpenAlexW2056508159MaRDI QIDQ1064779

Ivan Hal Sudborough, W. Michael Evangelist, 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

zbMATH Keywords

bandwidth bounded problemlog-space completespace bounded class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Unnamed Item, Bandwidth contrained NP-complete problems

Cites Work

• Unnamed Item
• Unnamed Item
• Bandwidth constraints on problems complete for polynomial time
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
• On the complexity of some problems concerning the use of procedures. II
• Space-bounded reducibility among combinatorial problems
• The NP-completeness of the bandwidth minimization problem
• Some simplified NP-complete graph problems
• Bandwidth contrained NP-complete problems
• Bandwidth and pebbling
• Relationships between nondeterministic and deterministic tape complexities
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Complexity Results for Bandwidth Minimization
• The complexity of satisfiability problems