2
$\begingroup$
  1. Apart from $2SAT$, what versions of SAT problem is complete for the class NL?

  2. Is there dynamic programming algorithm to solve the $2SAT$ Problem?

$\endgroup$
  • 2
    $\begingroup$ Is Gaussian elimination a dynamic programming algorithm? $\endgroup$ – JeffE Sep 7 '13 at 17:02
  • $\begingroup$ I am not at all sure, but I don't think so, (please correct me if I am wrong). Although Gaussian elimination does seem to have the structural feel of a a DP, i still can't come into agreement that it is essentially a DP $\endgroup$ – Subhayan Sep 7 '13 at 23:20
7
$\begingroup$

(1) is hard to answer unless you clarify what you mean by "versions of SAT problem." If we limit ourselves to the classes listed in Schaefer's "The Complexity of Satisfiability Problems", the only nontrivial class known to be in NL is 2-SAT.

As for question (2), 2-SAT is amenable to dynamic programming, as is SAT in general. During the DPLL process each partial assignment produces a new subformula: the previous formula with false literals removed and all satisfied clauses deleted. As subformulas are determined to be unsatisfiable, they can be memoized in a canonical form. If a known unsatisfiable subformula is encountered again during the DPLL search, a table lookup can identify it and the search can immediately backtrack. For SAT instances derived from problems with many symmetries (and therefore many identical subformulas) the time savings can be substantial.

$\endgroup$

Your Answer

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

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