티스토리 뷰
2-SAT(2-Satisfiability Problem)는 충족 가능성 문제 중 하나이며
논리식을 논리곱 정규형으로 표현 했을 때 각 절에 두 개의 변수만이 존재하는 경우
이 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제입니다.
k-SAT는 NP-완전이라는 것이 증명되었으나 2-SAT문제 만이 다항 시간내에 풀 수 있습니다.
논리곱 정규형으로 표현 된 절 중 하나인 (A∨B) 라는 절이 참이 되려면
A가 거짓이라면 B는 무조건 참이여야 하며, B가 거짓이라면 A는 무조건 참이여야 합니다.
이를 이용하여 ¬A → B 와 ¬B → A이라는 명제로 표현 될 수 있으며
모든 절을 합하여 하나의 유향그래프를 생성할 수 있습니다.
이제 이 그래프로 논리식이 참이 되는 변수값이 존재하는지 찾아야 하는데 조건은 아래와 같습니다.
1. 각 정점 A와 ¬A 중 하나는 참, 하나는 거짓이여야 한다.
2. 참 정점에서 거짓 정점으로 가는 경로는 없다.
(p → q에서 p가 참일 때는 q는 무조건 참이여야하며 p가 거짓일 때는 q가 무엇이든지 상관없음)
이러한 조건으로 인하여 하나의 사이클을 이루는 정점은
모두 참 정점이거나 모두 거짓 정점이여야하며 A와 ¬A이 같은 사이클에 있을 수 없습니다.
또한 현재 들어오는 간선이 하나도 없는 정점을 골랐을 때 이 정점을 거짓으로 분류해도 잃을 것이 없다는 것을 알 수 있습니다.
하나의 사이클을 이루는 정점을 하나의 정점으로 표현하기 위해 그래프를 앞서 배운 SCC로 분리하며,
모든 정점 A와 ¬A가 같은 사이클에 있지 않을 경우 이 그래프가 표현하는 논리식이 참이되는 변수값이 존재한다는 것이므로
현재 들어오는 간선이 하나도 없는 정점을 거짓으로 분류하기 위하여 앞서 배운 위상정렬을 사용합니다.
SCC의 특성에 따라 SCC는 위상정렬의 역순으로 번호가 매겨져 좀 더 쉽게 구할 수 있습니다.
이러한 2-SAT의 경우 2개의 선택지를 가지고 둘 중 하나는 최소한 만족해야하는 형태의 문제일 때 생각해 볼 수 있습니다.
기본 문제
