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

DOI10.1016/0166-218X(90)90020-DzbMath0679.68075WikidataQ123152755 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 problem; NP-complete; conjecture of Tovey

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

Related Items

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

Cites Work

• Unnamed Item
• 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