Reputation: 117
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?
Upvotes: 1
Views: 665