On the r,s-SAT satisfiability problem and a conjecture of Tovey
From MaRDI portal
Publication:1822964
DOI10.1016/0166-218X(90)90020-DzbMath0679.68075OpenAlexW2066022804WikidataQ123152755 ScholiaQ123152755MaRDI QIDQ1822964
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
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
- 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
This page was built for publication: On the r,s-SAT satisfiability problem and a conjecture of Tovey