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

DOI10.1007/978-3-642-45030-3_24zbMATH Open1406.68044OpenAlexW254497838MaRDI QIDQ2872090FDOQ2872090

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

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

Mathematics Subject Classification ID

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

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)