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

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

(36)

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

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)