[일반] 2SAT 이해좀 시켜줄사람

[페렛(quirrel)]

p V q를  ~p -> q, ~q -> p로 분해할 수 있다

식이 만족가능하려면 어떤 변수 p와 ~p가 서로 다른 scc에 있어야 한다

이때 타잔 기준으로 방문 번호가 클수록 DAG에서 뒤에 위치해있으니까

p의 방문번호를 num[p]라고 할때 p의 값은 num[p] < num[~p]로 나타낼 수 있다

다시말해 p가 앞에 위치해있다면 false, 뒤에 위치해있다면 true로 만들어주면 된다

이게맞음???

[익명(118.235)]

명제가 false 인건 항상 참이다를 이용하는거임

[익명(121.135)]

정확히 설명하자면, p, ~p로 구성된 그래프에서 p V q를 ~p -> q, ~q -> p로 만들어서 간선을 주면 어떤 True/False assignment가 feasible할 필요충분조건은 그래프에서 True -> False 간선이 없는 것임. 그런데 SCC 내에서는 모든 정점이 다른 모든 정점으로 갈 수 있기 때문에 SCC 내에서는 무조건 assignment가 모순되면 안 됨. 여기서 p와 ~p가 서로 다른 SCC에 있어야 한다는 조건이 나옴. 그런데 거꾸로 이 조건만 만족되면 feasible assignment를 찾을 수 있는데, 그 construction은 방문번호(topological sort 한 후 ordering) 기준으로 하면 됨. 그 이유는, 만약 모순이 발생한다면,

[익명(121.135)]

WLOG ~p -> q인데, 여기서 ~p가 True, q가 False라는 것임. 그런데 그래프를 구성한 방법에 의하여 ~q -> p도 존재하는데, 얘도 True -> False임. 그런데, 값을 할당한 방법을 잘 생각해보면, p와 ~p를 비교했을 때 p가 더 앞쪽에 왔을 것이고, 마찬가지로 ~q보다 q가 더 앞쪽에 왔을 것임. 그리고 간선이 있는 방향에 의해 ~p보다 q가 나중에 오고, ~q보다 p가 나중에 옴. 종합해보면 p 다음에 ~p 다음에 q 다음에 ~q 다음에 p가 나왔다는 이야기인데, 이는 SCC의 "supergraph"에 사이클이 존재하지 않음에 모순임.

[페렛(quirrel)]

오 훨씬 이해하기 편한듯ㄱㅅㄱㅅ