One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

DOI10.1137/0222015MaRDI QIDQ4037693zbMATH OpenOpenAlexFDO

Authors Jan Kratochvíl, Petr Savický, Zsolt Tuza

Publication date 16 May 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222015

zbMATH Keywords

NP-completenesssatisfiabilityBoolean formulaconjunctive normal form

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• A simplified NP-complete satisfiability problem
• On the parameterized complexity of \((k,s)\)-SAT
• The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
• Uniquely satisfiable k-SAT instances with almost minimal occurrences of each variable

Cited in

(38)

• A CNF Class Generalizing Exact Linear Formulas
• Deciding Relaxed Two-Colourability: A Hardness Jump
• The Helly property and satisfiability of Boolean formulas defined on set families
• scientific article; zbMATH DE number 2089957 (Why is no real title available?)
• DNF tautologies with a limited number of occurrences of every variable
• On the complexity of path problems in properly colored directed graphs
• A simplified NP-complete satisfiability problem
• The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant
• Uniquely satisfiable k-SAT instances with almost minimal occurrences of each variable
• A simplified NP-complete MAXSAT problem
• Satisfiability with index dependency
• XSAT and NAE-SAT of linear CNF classes
• Inapproximability of counting hypergraph colourings
• Fractal structure on k-SAT
• Disproof of the neighborhood conjecture with implications to SAT
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• How Many Conflicts Does It Need to Be Unsatisfiable?
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• Boundary properties of the satisfiability problems
• The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
• scientific article; zbMATH DE number 1678383 (Why is no real title available?)
• Small unsatisfiable k-CNFs with bounded literal occurrence
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• Mathematical Foundations of Computer Science 2003
• The Lovász Local Lemma and Satisfiability
• Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
• Efficient computation of sparse structures
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• Hard constraint satisfaction problems have hard gaps at location 1
• Computational complexity of some restricted instances of 3-SAT
• Algorithmic complexity of list colorings
• Improved \textsc{MaxSAT} algorithms for instances of degree 3
• On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• On the parameterized complexity of \((k,s)\)-SAT
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Comparison of two convergence criteria for the variable-assignment lopsided Lovász local lemma

This page was built for publication: One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

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