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 n path paterns as n different boolean variables belonging to an "AND group of clauses". "Clause" being "an OR group" composed of conditions over some of the n variables.
    example : of a SAT problem being "find values of x1, x2, x3 such that clause1 AND clause2 AND clause3 is true", with clause1 being x1 OR x2 (is true), clause2 being x1 OR NOT(x3), etc.
  • m added vertices to force the m clauses 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

  • $\begingroup$ It's really impossible to tell, since the rest of the video is missing. But according to the video, the number of diamonds should be at least the number of clauses using the variable. Since this is at most $m$, having $m$ diamonds will surely work. $\endgroup$ – Yuval Filmus Apr 4 '20 at 7:26
  • $\begingroup$ Note that SAT is NP-hard while shortest path is in P. So you won't be able to reduce SAT to shortest path. $\endgroup$ – Yuval Filmus Apr 4 '20 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.