0
$\begingroup$

Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. My first guess would be that somehow the satisfiability of sub-clauses is stored for later reference, but I'm not completely sure. Any help is appreciated!

(First time posting, apologies if this is the wrong place/format)

$\endgroup$
3

1 Answer 1

3
$\begingroup$

It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here are some hints which might put you on the path to the solution:

  1. Remember the definition of 2-SAT;
  2. Remember the logical definition of A => B in term of 'not', 'and' and 'or' operators;
  3. See how you would solve an instance of 2-SAT "by hand", without trying to do so in linear time (but still trying to be efficient);
  4. Analyze the running time of your algorithm to solve a 2-SAT instance (hopefully it should be at least polynomial);
  5. Remember how many dimensions are used by the tables in dynamic programs running in linear time;
  6. Think about the size of a table of the same number of dimension which could solve a 2-SAT instance (i.e. is it as big as a function of the number of variables or of the number of clauses);
  7. Deduce a dynamic program solving a 2-SAT instance in linear time (and space).

Hopefully you don't hate this answer because, voluntarily, it avoids giving you the solution! I tried to put just the right amount of hints towards the solution so that you could get unstuck if you are, but with enough room for you (and other future readers) to still learn from the experience!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.