1

I have a problem which is an extension of 2-SAT problem. In standard 2-SAT problem, we can find any of the truth assignments which depends on the ordering of vertices we choose. I want to check whether there exists one and only one truth assignment(i.e only one combination) for which the expression is satisfiable. The number of literals can be 100000. One way is to find all the possible truth assignments, then compare them if they are distinct. But the problem is for each comparison, I will have to compare 100000 values(no of literals). Is there any efficient way?

avd
  • 13,993
  • 32
  • 78
  • 99

1 Answers1

1

Feder (1994) describes an algorithm for efficiently listing all solutions to a given 2-satisfiability instance. There are also citations in the article for algorithms to count the number of assignments, but you only need to try listing two assignments, which may be more efficient.

Martin Hock
  • 944
  • 4
  • 5
  • Thank you very much. Can you provide me the link for the paper in pdf? – avd Nov 03 '09 at 04:12
  • Here's one for one of the counting papers. http://www.cse.psu.edu/~kasivisw/2sat.pdf Tomas Feder's website doesn't contain a link to the 1994 paper. – Martin Hock Nov 03 '09 at 05:04
  • Just a comment: the paper I sent you to is for an exponential time algorithm. I suppose then that you want to use Feder's algorithm, which appears to be polynomial time. You can purchase it here for $34, or you can find a copy of Algorithmica at your local research library. http://www.springerlink.com/content/j582276p06276l12/ – Martin Hock Nov 03 '09 at 05:09