suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas actually are generated by another algorithm which creates/ generates instances $F_n$ for any $n$. the solving algorithm can find/ exploit "similar structures" contained in each by analyzing eg the clause-variable graph, eg looking for graph isomorphisms etc.

has this problem of finding "similarities" between two SAT formulas by a solver been studied?

there is some rough connection of this eg implications of worst case bounds in this paper A simple proof that AND-compression of NP-complete problems is hard (Dell), but am looking for more direct algorithm(s) and possibly more empirical approaches/ analysis, eg somewhat similar to strategies/ heuristics used in SAT solver implementations. (this problem has applications in eg automated theorem proving.)

  • 3
    $\begingroup$ There are sat portfolios like satzilla that use machine learning to try to identify which solver is the best. But not sure if that's what you're looking for. If the set of variables remains the same, one easy technique would be to keep activities and polarities from the last formula for the next one. $\endgroup$ – Mikolas Jul 26 '14 at 9:55
  • 1
    $\begingroup$ "Learning" is an important componant of most sat solvers. In particular, finding interpolants between formulas is an active area for improving or making feasible the proof of certain difficult SAT instances. Conceivably, finding an interpolant between a proven instance P and an unproven one Q may help prove Q more quickly. I think this is a very interesting question! $\endgroup$ – cody Jul 27 '14 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.