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

DOI10.1137/0222015zbMath0767.68057OpenAlexW2000171675MaRDI QIDQ4037693

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)

Related Items (22)

Algorithmic complexity of list colorings ⋮ A simplified NP-complete MAXSAT problem ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Satisfiability with index dependency ⋮ Improved MaxSAT Algorithms for Instances of Degree 3 ⋮ The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs ⋮ Computational complexity of some restricted instances of 3-SAT ⋮ Disproof of the neighborhood conjecture with implications to SAT ⋮ On the complexity of path problems in properly colored directed graphs ⋮ A CNF Class Generalizing Exact Linear Formulas ⋮ How Many Conflicts Does It Need to Be Unsatisfiable? ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ XSAT and NAE-SAT of linear CNF classes ⋮ On the parameterized complexity of \((k,s)\)-SAT ⋮ Deciding Relaxed Two-Colourability: A Hardness Jump ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ Efficient computation of sparse structures ⋮ The Lovász Local Lemma and Satisfiability ⋮ DNF tautologies with a limited number of occurrences of every variable ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma ⋮ The \(k\)-SATISFIABILITY problem remains NP-complete for dense families

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