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?
+1
A:
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
2009-11-03 04:07:16
Thank you very much. Can you provide me the link for the paper in pdf?
avd
2009-11-03 04:12:49
Here's one for one of the counting papers.http://www.cse.psu.edu/~kasivisw/2sat.pdfTomas Feder's website doesn't contain a link to the 1994 paper.
Martin Hock
2009-11-03 05:04:06
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
2009-11-03 05:09:05
Thank you very much for your help.
avd
2009-11-03 05:34:19
A:
Hi Lex, Have you been able to find the asnwer to your question? I thought that if we can find any one variable whose complement node is not reachable from its actual node then there will be multiple assignment but that will req complexity O(n*n) as for each variable we will have to test. Did you find a better method?
Saty
2009-11-09 17:08:32