我读了许多用于找到2-SAT问题的算法,即给定表达式是否可满足,可以在多项式时间内求解.例子(算法).
对于Krom的程序(维基百科),我构建了图,我可以从中轻松验证其在多项式时间内的可满足性.
现在,我想找到这个表达式的解决方案是可以满足的.
我这样想(验证它):首先我采用形成强连通分量的任何字面表示x,并将值赋值为0.然后根据算法,存在edge(x! - > y).因此y不能为0.(因为1 - > 0是假的)并且如果可能的话同样地进行.
否则取x = 0,然后只选择y = 1,同样继续获得任何可满足的实例.
现在,是在多项式时间内找到任何一个的任何可行解决方案
对于这类问题,我没有得到任何多项式算法.