in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences),
whose purpose is to show how a SAT problem can be solved as the shortest path problem would be,
I understand that
- there are
npath paterns as
ndifferent boolean variables belonging to an "
ANDgroup of clauses". "Clause" being "an
ORgroup" composed of conditions over some of the
example : of a SAT problem being "find values of
x1, x2, x3such that
clause1 AND clause2 AND clause3is true", with clause1 being
x1 OR x2(is true), clause2 being
x1 OR NOT(x3), etc.
madded vertices to force the
mclauses to be ensured while having an unique "local" shortest path (within a local pattern)
But the thing I don't understand is why each pattern has to have
3(m+1) vertices? Why 2 diamonds per pattern isn't sufficient ?
Thank you for enlighting me