开发者

2-Satisfiability problem-Whether a unique truth assignment exists or not

开发者 https://www.devze.com 2022-12-10 13:38 出处:网络
I have a problem which is an extension of 2-SAT problem. In standard 2-SAT problem, we can 开发者_如何学Cfind any of the truth assignments which depends on the ordering of vertices we choose. I want t

I have a problem which is an extension of 2-SAT problem. In standard 2-SAT problem, we can 开发者_如何学Cfind 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?


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.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号