Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas

DOI10.1007/978-3-642-45030-3_24MaRDI QIDQ2872090zbMATH OpenOpenAlexFDO

Authors D. Scheder

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• On Linear CNF Formulas
• Why almost all satisfiable k-CNF formulas are easy
• Linear CNF formulas and satisfiability

Cited in

(5)

• Proving unsatisfiability of CNFs locally
• Proving unsatisfiability of CNFs locally
• How Many Conflicts Does It Need to Be Unsatisfiable?
• On the CNF-complexity of bipartite graphs containing no squares
• Unsatisfiable CNF formulas contain many conflicts

This page was built for publication: Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas

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