Bandwidth constraints on problems complete for polynomial time

DOI10.1016/0304-3975(83)90078-6zbMATH Open0535.68021OpenAlexW2053805167WikidataQ127662435 ScholiaQ127662435MaRDI QIDQ791316FDOQ791316

Authors: I. H. Sudborough 

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90078-6

Recommendations

• Complete problems for space bounded subclasses of NP
• Bandwidth contrained NP-complete problems
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
• A positive relativization of polynomial time versus polylog space
• Decreasing the bandwidth of a transition matrix

zbMATH Keywords

bandwidth constraintspath system problemtime-space alternating classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• On uniform circuit complexity
• Relationships between nondeterministic and deterministic tape complexities
• Relations Among Complexity Measures
• Alternation
• An observation on time-storage trade off
• Title not available (Why is that?)
• The NP-completeness of the bandwidth minimization problem
• Complexity Results for Bandwidth Minimization
• On Relating Time and Space to Size and Depth
• The bandwidth problem for graphs and matrices—a survey
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• An algorithm for reducing the bandwidth of a matrix of symmetrical configuration
• On tape-bounded complexity classes and multihead finite automata
• On the Tape Complexity of Deterministic Context-Free Languages
• Space-bounded reducibility among combinatorial problems
• Some Results on Tape-Bounded Turing Machines
• Tree-size bounded alternation
• Minimizing the bandwidth of sparse symmetric matrices
• Title not available (Why is that?)
• An extension of Savitch's theorem to small space bounds
• Space bounds for processing contentless inputs
• Lower bounds on space complexity for contextfree recognition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Complete problems for space bounded subclasses of NP
• Topological Bandwidth
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Alternating on-line Turing machines with only universal states and small space bounds
• Bandwidth contrained NP-complete problems

This page was built for publication: Bandwidth constraints on problems complete for polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q791316)