Problem Detail: I’m trying to wrap my head around an NP-completeness proof which seem to revolve around SAT/3CNF-SAT. Maybe it’s the late hour but I’m afraid I can’t think of a 3CNF formula that cannot be satisfied (I’m probably missing something obvious). Can you give me an example for such formula?
Asked By : user11171
Answered By : Shaull
Technically, you can write $xwedge neg x$ in 3-CNF as $(xvee xvee x)wedge (neg xvee neg xvee neg x)$, but you probably want a “real” example. In that case, a 3CNF formula needs at least 3 variables. Since each clause rules out exactly one assignment, that means you need at least $2^3=8$ clauses in order to have a non-satisfiable formula. Indeed, the simplest one is: $$(xvee yvee z)wedge (xvee yvee neg z)wedge (xvee neg yvee z)wedge(xvee neg yvee neg z)wedge(neg xvee yvee z)wedge(neg xvee yvee neg z)wedge(neg xvee neg yvee z)wedge(neg xvee neg yvee neg z)$$ It is not hard to see that this formula is unsatsifiable.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/20117
