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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Is Gaussian elimination a dynamic programming algorithm? $\endgroup$
    – JeffE
    Sep 7, 2013 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, 2013 at 23:20

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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