On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas

DOI10.1016/0304-3975(89)90125-4zbMath0687.03018OpenAlexW2066728092MaRDI QIDQ1262855

K. Appert

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90125-4

zbMATH Keywords

satisfiabilitySATCNF formulalog-bandwidth constrained formulaNP- complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Related Items (1)

Padding, commitment and self-reducibility

Cites Work

• Natural Self-Reducible Sets
• On self-transformable combinatorial problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas