Problem Detail: I’m having some trouble understanding the following: When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining the variables. For eg. here is a randomly generated 3-CNF sentence with five symbols and five clauses. (Each clause contains 3 randomly selected distinct symbols, each of which is negated with 50% probability.)
(¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)
16 of the 32 possible assignments are models of this sentence, so, on an average, it would take just 2 random guesses to find the model. I don’t understand the last line- saying that there are 32 possible assignments. How is it 32? And how are only 16 of them models of the sentence? Thanks.
Asked By : Ghost
Answered By : Dave Clarke
There are 5 (Boolean) variables in the formula. Each of these could be either true or false. This means that there are $2^5=32$ ways of assigning values to these variables. Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4729 3.2K people like this
