As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [sat-solvers]

Questions regarding solver programs for the boolean satisfiability problem.

Filter by
Sorted by
Tagged with
32 votes
3 answers
6k views

Encoding 1-out-of-n constraint for SAT solvers

I'm using a SAT solver to encode a problem, and as part of the SAT instance, I have boolean variables $x_1,x_2,\dots,x_n$ where it is intended that exactly one of these should be true and the rest ...
D.W.'s user avatar
  • 152k
19 votes
3 answers
966 views

Recipe book for SAT encodings?

SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts. Every time one wants to use them to solve a problem in a specific domain,...
Bordaigorl's user avatar
19 votes
1 answer
3k views

When to use SAT vs Constraint Satisfaction?

If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, ...
D.W.'s user avatar
  • 152k
20 votes
1 answer
4k views

Proving that the conversion from CNF to DNF is NP-Hard

How can I prove that the conversion from CNF to DNF is NP-Hard? I'm not asking for an answer, just some suggestions about how to go about proving it.
jkjk's user avatar
  • 301
6 votes
2 answers
239 views

Convert $\sum x_i = y$ to 3-sat

I have a simple looking question. What is the most efficient conversion of $\sum_{i=1}^n x_i = y$ to 3-sat? Here $x_i$ is either $1$ or $0$ and $y$ is some positive integer. Can you do better than ...
Simd's user avatar
  • 860
2 votes
2 answers
2k views

Best improvements to do to the DPLL SAT algorithm

As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select ...
user1843790's user avatar
6 votes
2 answers
5k views

Understanding DPLL algorithm

I'm trying to understand DPLL algorithm for solving SAT problem. And here it is: ...
Tikhon Belousko's user avatar
1 vote
0 answers
136 views

Logical formula in DIMACS, SAT, Schaefer's dichotomy theorem and software to test it

I have a very complicated formula logical (CNF) in the file DIMACS. The question is as follows. The formula has hundreds of millions of clauses (assume billion) and a lot of variables. It is a ...
Aurelio's user avatar
  • 239
1 vote
4 answers
2k views

Is this possible to solve 3SAT in O(n^24) time and O(1) space?

Assume that n is the number variables of the given 3CNF formula (n≥3) and all clauses in the given 3CNF formula are different. That means that for each clause, each literal can be either positive ...
Farewell Stack Exchange's user avatar
0 votes
1 answer
117 views

Encoding a "not-k-out-of-n" constraint for SAT solvers

I'm finding myself needing to encode a "not-k-out-of-n" constraint in a SAT solver. The "at-most-k-out-of-n" constraint for SAT solvers is something I can find research about -- this paper by Frisch ...
onigame's user avatar
  • 193
-2 votes
1 answer
263 views

How a SMT / SAT Solver Generates Valuations for this Example

First, an example of a set of constraints which turned out not to be solvable (I don't think): ...
Lance's user avatar
  • 2,103