Skip to main content
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 285

Mapping Problemsproblems to Boolean Formulasformulas for SAT Solverssolvers

Typos in the title are corrected.
Link
user64494
  • 3.5k
  • 14
  • 22

Mapping Problems to Boolean formulasFormulas for SAT solversSolvers

added 1 character in body
Source Link
Mario Krenn
  • 155
  • 12
  • 35

I came across MajinMarijn Heule and Oliver Kullmann's paper on recent techniques in highly efficient SAT solvers. In particular they describe the Pythagorian Triple Problem, which they solved using that method one year earlier (a problem that was open for several decades, and had a monetary reward by Ronald Graham). Another famous example is the computer-aided special case solution for Erdős's discrepancy problem (before it was generally solved by Terence Tao).

I would like to know whether there is some comprehensive literature on techniques how to map some problems to SAT problems. Otherwise, I would also like to know other special solutions that have been achieved with SAT solvers, using a mapping from a problem in some field to boolean formulars. Are there special methods that are commonly used, or does one has to think about the mapping very specifically from problem to problem?

I came across Majin Heule and Oliver Kullmann's paper on recent techniques in highly efficient SAT solvers. In particular they describe the Pythagorian Triple Problem, which they solved using that method one year earlier (a problem that was open for several decades, and had a monetary reward by Ronald Graham). Another famous example is the computer-aided special case solution for Erdős's discrepancy problem (before it was generally solved by Terence Tao).

I would like to know whether there is some comprehensive literature on techniques how to map some problems to SAT problems. Otherwise, I would also like to know other special solutions that have been achieved with SAT solvers, using a mapping from a problem in some field to boolean formulars. Are there special methods that are commonly used, or does one has to think about the mapping very specifically from problem to problem?

I came across Marijn Heule and Oliver Kullmann's paper on recent techniques in highly efficient SAT solvers. In particular they describe the Pythagorian Triple Problem, which they solved using that method one year earlier (a problem that was open for several decades, and had a monetary reward by Ronald Graham). Another famous example is the computer-aided special case solution for Erdős's discrepancy problem (before it was generally solved by Terence Tao).

I would like to know whether there is some comprehensive literature on techniques how to map some problems to SAT problems. Otherwise, I would also like to know other special solutions that have been achieved with SAT solvers, using a mapping from a problem in some field to boolean formulars. Are there special methods that are commonly used, or does one has to think about the mapping very specifically from problem to problem?

Fixed spelling
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55
Loading
edited tags
Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152
Loading
Source Link
Mario Krenn
  • 155
  • 12
  • 35
Loading