On the r,s-SAT satisfiability problem and a conjecture of Tovey

DOI10.1016/0166-218X(90)90020-DzbMath0679.68075OpenAlexW2066022804WikidataQ123152755 ScholiaQ123152755MaRDI QIDQ1822964

Olivier Dubois

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90020-d

zbMATH Keywords

satisfiability problemNP-completeconjecture of Tovey

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (7)

Computational complexity of some restricted instances of 3-SAT ⋮ Tensor network contractions for \#SAT ⋮ On the parameterized complexity of \((k,s)\)-SAT ⋮ Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable ⋮ Counting the number of solutions for instances of satisfiability ⋮ How good are branching rules in DPLL? ⋮ DNF tautologies with a limited number of occurrences of every variable

Cites Work

• A simplified NP-complete satisfiability problem
• The Euclidean traveling salesman problem is NP-complete
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
• On the Complexity of Timetable and Multicommodity Flow Problems
• Two-Processor Scheduling with Start-Times and Deadlines
• On Representatives of Subsets
• Unnamed Item

This page was built for publication: On the r,s-SAT satisfiability problem and a conjecture of Tovey