1

I am a bit confused. I know how to reduce 3-SAT to IS. An example of transforming 3-SAT to IS graph would be create a graph representing each clause of the 3-SAT and then joining the x and !x and then submitting it to IS. How would we apply this to a more generic SAT <=p IS reduction, without reducing SAT to 3-SAT? To me it seems like it would be the same way, but I have a feeling that is not the case and I am missing something. An instance of SAT: 

x1 ∧ (x2 ∨ ̄x1) ∧ (x3 ∨ x4 ∨ ̄x2)

Would we transform this in the same way, and is there a generic sequence of steps to use for all instances of SAT? How would I prove it?

lazycamper
  • 107
  • 1
  • 8
  • As you have already the feeling that a small variation of the generic procedure does not work: Can you describe your method based on an example? – tphilipp May 08 '20 at 19:56
  • With the above given SAT formula, the graph edges would be: [(x1, !x1), (x2, !x1), (x3, x4), (x4, !x2), (x2, !x2)]. With this graph, we could submit it to the black box of IS with the input as number of clauses and if it returns true, then we have a satisfiable formula. @tphilipp – lazycamper May 08 '20 at 20:45

0 Answers0