社区讨论

2-SAT 一个震惊的问题

学术版参与者 7已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mc5prax3
此快照首次捕获于
2025/06/21 12:03
8 个月前
此快照最后确认于
2025/11/04 07:03
4 个月前
查看原帖
其中 iiii' 表示这个 aia_i 的两种状态。
这是显然有解的,没有 iiii' 在同一强联通分量里。由于我们选 scc 小者,解应为 11'22'33'44'
但是问题就在这里,如果我们选了 22' 就应该选 33,选了 33 就应该选 44,选了 44 就应该选 33',这不就矛盾了?!
我不知道真实情况中会不会出现这种图的存在情况,但我认为如果出现这种情况的话,岂不是 2-SAT 就崩塌了?

回复

10 条回复,欢迎继续交流。

正在加载回复...