Complete problems for space bounded subclasses of NP

DOI10.1007/BF00288774MaRDI QIDQ1064779zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

bandwidth bounded problemlog-space completespace bounded class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bandwidth contrained NP-complete problems
• Bandwidth constraints on problems complete for polynomial time
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
• scientific article; zbMATH DE number 2156275
• On problems with short certificates

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Bandwidth and pebbling
• Bandwidth constraints on problems complete for polynomial time
• Bandwidth contrained NP-complete problems
• Complexity Results for Bandwidth Minimization
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• 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
• Relationships between nondeterministic and deterministic tape complexities
• Some simplified NP-complete graph problems
• Space-bounded reducibility among combinatorial problems
• The NP-completeness of the bandwidth minimization problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The complexity of satisfiability problems

Cited in

(12)

• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• Bandwidth contrained NP-complete problems
• 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
• scientific article; zbMATH DE number 6482141 (Why is no real title available?)
• Bandwidth constraints on problems complete for polynomial time
• Some remarks on subclass containment problems for several classes of dpda's
• scientific article; zbMATH DE number 3954277 (Why is no real title available?)
• scientific article; zbMATH DE number 2107051 (Why is no real title available?)
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas

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)