[LowWaterMark]

Equality reduction and satisfiability testing (SAT): I'm stuck.

I just finished watching the ADUni.org Discrete Math video lecture that covered reduction and satisfiability (topic starts @ 53:01 of lecture #2 - see above link). I was left in the dust.

My Google search directed me into a universe of graduate level scholarly papers on the subject but nothing in the way of an introduction. Is anyone aware of an online site that gently introduces these two interrelated subjects?

Thanks for reading.

This post has been edited by LowWaterMark: 20 October 2008 - 03:16 AM

[MindWater]

LowWaterMark, on 20 Oct, 2008 - 02:38 AM, said:

Equality reduction and satisfiability testing (SAT): I'm stuck.

I just finished watching the ADUni.org Discrete Math video lecture that covered reduction and satisfiability (topic starts @ 53:01 of lecture #2 - see above link). I was left in the dust.

My Google search directed me into a universe of graduate level scholarly papers on the subject but nothing in the way of an introduction. Is anyone aware of an online site that gently introduces these two interrelated subjects?

Thanks for reading.

I would probably pick up Introduction to the Theory of Computation by Michael Sipser, it has a pretty good introduction to both Equality reduction and satisfiability, atleast in my oppinion, we just had our lectures on this, and it seemed pretty clear from the reading.

[chrisesposito]

LowWaterMark, on 20 Oct, 2008 - 01:38 AM, said:

Equality reduction and satisfiability testing (SAT): I'm stuck.

I just finished watching the ADUni.org Discrete Math video lecture that covered reduction and satisfiability (topic starts @ 53:01 of lecture #2 - see above link). I was left in the dust.

My Google search directed me into a universe of graduate level scholarly papers on the subject but nothing in the way of an introduction. Is anyone aware of an online site that gently introduces these two interrelated subjects?

Thanks for reading.

Have you looked at Garey and Johnson's book: http://www.amazon.co...s/dp/0716710455

I thought their discussion of these problems was pretty clear when I was in grad school.

[Programmist]

My bet is that if he's having trouble with these topics that the Sipster book will probably be way too terse for him. Very good book - just not really for beginners.

Edit: Dammit. I just noticed this thread had been resurrected by the previous poster.

This post has been edited by Programmist: 05 January 2009 - 12:55 PM