이 문제는 3-coloring 문제와 연관시켜 푸는게 좋다. 즉 3-coloring보다 1-in-3 sat이 더 어렵다는 것을 보이면 (즉 1-in-3-sat을 풀 수 있다면 3-coloring 을 풀 수 있다는 것을 보이면 된다.) 3-coloring이 np complete임을 아므로, 자연스럽게 증명이 된다. 3-coloring문제를 다음과 같이 해석해보자. 각 정점 v에 대해서 v의 색깔 red,blue,green에 대한 세 변수 Rv,Bv,Gv를 만든다. 이 변수는 v가 red라면 Rv만 true이고, 나머지는 false이다. 모든 색에 대해 동일하게 적용된다. 그렇다면 (Rv or Bv or Gv)라는 clause를 각 v에 대해 만든다. 그 후 모든 edge (a,b)에 대해 다음과 같은 clause들을 추가로 만든다. (Ra or Rb or Rab) (Ba or Bb or Bab) (Ga or Gb or Gab) 여기서 Rab, Bab,Gab는 dummy variable이다. 이렇다면 1-in-3 sat은 단 1개만 true여야 하기 때문에 Ra 나 Rb중 한 개만 true 일 수 있다. (이는 3-coloring문제와 동일) 마찬가지로 3-coloring과 동일하게 된다.
따라서 1-in-3sat을 풀면 3-coloring을 풀 수 있으므로 1-in-3sat은 np complete이다.
이 문제는 수업중 예제 문제와 비슷했다.
Threshold 2-sat은 minimum vertex cover로 살펴보자.
즉 어떤 clause (U or V)에 대해서, edge(u,v)를 잇자.
이렇게 되면 t개 이하의 true를 사용할 수 있는 지 판단하는 것은 mimium vertex cover을 구하는 문제와 동치이다.
따라서 np-complete
다음 문제는 너무 어려운 문제였다... 다들 도전해 보시길...
직관적으로 independent set problem과 동치임을 보이자. (정의가 꽤 닮아있다.)
이제 새로운 그래프 G'을 정의한다. 이 G'은 G와 거의 동일한데, 모든 G에 포함된 정점 v에 대해서 v'이라는 새로운 정점을 만들고 v와 v'을 잇는 간선을 연결한 새로운 그래프이다.
이 G에서의 independent set을 구하는 것과 G'에서 cellphone capacity를 구하는 것이 동치임을 보이면 끝이다.
근데 이게 좀 어렵다 ㅜ (애초에 여기까지 발상도 어렵다)
문제들은 reduction 시키는 것이 더 쉬울때가 많은데, 이 문제는 one to one 대응이 있음을 보인다.
즉 한쪽에서 yes라면 반대쪽에서 yes인 것을 양방향으로 보일 것임. ( 결정 문제 이므로)
G에서 크기 k의 independent set이 있다면 G'에서 크기 k의 cellphone capacity를 구할 수 있다
G에서 크기 k의 independent set을 S라 하자. S에 포함된 모든 정점 vi 들에 대해서, (vi,vi') edge를 전부 모으면 G'에서 cellphone capacity k인 것이 된다.
반대 방향을 보자.
G'에서 크기 k의 cellphone capacity를 가진 집합이 있으면 G에서 크기 k의 independent set을 찾을 수 있을까?
간선 집합에서 원래 정점 v-v'연결꼴은 v를 선택하고, u-v연결꼴 (원래 G에 있던 두 정점을 연결하는 간선)은 아무거나 선택하면 k-independent set을 찾을 수 있다.
따라사서 증명완료...
어렵다
'알고리즘 공부 > The nature of computation' 카테고리의 다른 글
| 퀴즈 (4) | 2022.11.29 |
|---|---|
| 공부 (1) | 2022.11.29 |