piy*_*ani 1 algorithm complexity-theory satisfiability 2-satisfiability
我读了许多用于找到2-SAT问题的算法,即给定表达式是否可满足,可以在多项式时间内求解.例子(算法).
对于Krom的程序(维基百科),我构建了图,我可以从中轻松验证其在多项式时间内的可满足性.
现在,我想找到这个表达式的解决方案是可以满足的.
我这样想(验证它):首先我采用形成强连通分量的任何字面表示x,并将值赋值为0.然后根据算法,存在edge(x! - > y).因此y不能为0.(因为1 - > 0是假的)并且如果可能的话同样地进行.
否则取x = 0,然后只选择y = 1,同样继续获得任何可满足的实例.
现在,是在多项式时间内找到任何一个的任何可行解决方案
对于这类问题,我没有得到任何多项式算法.
提供表达式可满足的所有可能解决方案
不,因为可能会有很多指数.
或者这个表达式对于具有总k literals = 1的输入是可满足的
不,因为如果这很容易,那么加权2可满足性(NP-hard)也是如此.
或者,为了满足表达式,有多少最小文字数值为1
这是加权2-SAT.