One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
From MaRDI portal
Publication:4037693
DOI10.1137/0222015zbMATH Open0767.68057OpenAlexW2000171675MaRDI QIDQ4037693FDOQ4037693
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
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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (33)
- A CNF Class Generalizing Exact Linear Formulas
- Deciding Relaxed Two-Colourability: A Hardness Jump
- Title not available (Why is that?)
- The Helly property and satisfiability of Boolean formulas defined on set families
- 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
- Improved MaxSAT Algorithms for Instances of Degree 3
- 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
- Fractal structure on \(k\)-SAT
- Disproof of the neighborhood conjecture with implications to 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
- The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
- Title not available (Why is that?)
- 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
- 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
- Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma
- Algorithmic complexity of list colorings
- Computational complexity of some restricted instances of 3-SAT
- On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
- A Complexity Dichotomy for the Coloring of Sparse Graphs
- On the parameterized complexity of \((k,s)\)-SAT
- Computing unsatisfiable \(k\)-SAT instances 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)
