Complete problems for space bounded subclasses of NP

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

• 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

zbMATH Keywords

bandwidth bounded problemlog-space completespace bounded class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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)