On Tue, 2020-05-19 at 09:55 -0700, R. Kudos wrote:
> Are there any parameters that allow generating a smaller SAT encoding
> the expense of a (presumably) more difficult problem for the SAT
Not really, no. On modern hardware, time tends to be the bottleneck
before memory. In cases where memory is a bottleneck, there tend to be
other things that you can do (i.e. incremental or lazy encoding,
slicing, etc.) that are more effective than making the problem more
time-intensive to solve.
> For example, I think of the log encoding as an example in SAT circles
> is generally thought to propagate poorly and thus requires more solve
> but has a smaller CNF formula.
I am not quite sure what you mean by the log encoding. If you are
referring to the encoding from CSP to SAT where you encode the choice
of one element from a domain of D things by using log_2(D) bits so that
they give a binary number picking the element, then, yes, we already do
that. That's how you can reason about int64_t without running out of
> I'm hoping to be able to do this without reducing the scope of the
> that are detected by the prover.
As long as the encoding is logically equivalent or at least
equisatisfiable it should be fine.
> So in other words, is it possible to represent the same problem but
> using a more concise CNF encoding at the expense of it probably being
> more difficult problem for the SAT solver to solve?
I am not aware of any ways of doing this, nor do I think it would be a
particularly useful trade-off. There are ways that the encodings can
be improved (I am working on some) but I don't think "more compact but
harder" is the way to go.