P, NP 문제 (2)
01 Dec 2017 | Max Flow Algorithm Ford-Fulkerson Algorithm Graph
이번 글에서는 P/NP 문제에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의를 정리했음을 먼저 밝힙니다. 이 문제에 대한 개괄적인 내용은 이곳을 참고하시면 좋을 것 같습니다. 그럼 시작하겠습니다.
용어 정리
용어 및 개념 몇 가지 정리하고 넘어가겠습니다(이해를 돕기 위한 비공식적인 정의).
- Class $P$란 다항시간(polynomial time) 내에 풀리는 문제를 가리킵니다.
- Class $NP$란 운이 좋으면 다항시간에 풀리는(nondeterministic polynomial) 문제로, 어떤 답이 해당 문제의 정답인지 여부를 다항시간 내에 확인(verified)할 수 있는 문제를 가리킵니다.
- $NP$-hard란 모든 $NP$ 문제를 해당 문제로 바꿔풀 수 있을(reduce) 때 해당 문제를 가리킵니다.
- $NP$-complete란 $NP$-hard이면서 Class $NP$에 속하는 문제를 가리킵니다.
- Reducibility란 어떤 문제 $P$를 $Q$로 바꿔풀 수 있는 경우를 가리킵니다. 만일 $P$가 $Q$로 reduce할 수 있다면, $P$는 $Q$보다 해결하기가 어렵지 않다고 말할 수 있습니다.
$P$, $NP$, $NP$-complete 사이의 관계는 다음과 같습니다.
위 다이어그램을 바탕으로 다음과 같은 사실을 확인할 수 있습니다.
- $NP$ 바깥의 영역은 어떤 답이 해당 문제의 정답인지 여부를 다항시간 내에 확인할 수 없는 문제들을 가리킵니다. 다시 말해 어떤 case가 맞는지조차 알기 어려운, 미지의 문제라는 뜻입니다.
- $P≠NP$-complete입니다.
- $NP$ 문제는 다항시간 내에 풀 수 있는지 없는지 아직 모르는 문제를 가리킨다면, $NP$-complete는 절대 다항시간 내에 풀 수 없다는 게 증명된 문제를 가리킵니다.
내 알고리즘이 어떤 부류인지 판단하기
내가 만든 알고리즘 $L$이 $NP$-complete인지 아닌지 판단하는 일반적인 절차는 다음과 같습니다. 이미 알려져 있는 $NP$-complete를 지렛대 삼아 판별하는 방법입니다.
-
$L$이 $NP$임을 증명 : 내가 만든 $L$에 대한 어떤 답이 $L$의 정답인지 여부를 다항시간 내에 확인할 수 있는지를 체크
-
$L$이 $NP$-hard임을 증명
(1) 내가 만든 $L$과 가장 유사한, 이미 증명된 $NP$-complete 문제를 찾는다.
(2) $L$을 (1)에서 찾은 $NP$-complete 문제로 바꾸고, 그 역도 가능한 함수 $f$를 정의한다.
(3) (2)에서 정의한 $f$가 다항시간 내에 작동하는지를 증명한다.
판별 예시
내가 만든 알고리즘 $L$이 $NP$-complete인지 아닌지 판단하는 예시(그림 출처)를 들어보겠습니다. 레지스터 할당에 쓰이는 Interference Graph를 $L$이라고 칩시다. 이것이 $NP$-complete인지 여부를 알아내는 것이 목표입니다.
Interference Graph란 코드 시퀀스에서 둘 이상의 변수가 겹쳐 등장할 경우 엣지를 연결해두는 그래프입니다. 둘 이상의 변수를 한 레지스터에 동시에 할당하는 걸 피하기 위해서입니다.
예컨대 변수 $A$는 line 1부터 line 5까지, $B$는 line 2부터 line 3까지 살아 있어야 하고, 2~3 line에서 둘이 겹치기 때문에 Interference Graph에서 둘 사이에 엣지를 연결해 줍니다. 이렇게 만들어진 Interference Graph에서 이웃한 노드들끼리는 서로 다른 레지스터에 변수를 할당해주는 겁니다.
우선 $L$이 $NP$임을 증명해 봅시다. Interfence Graph가 주어져 있을 때, 서로 이웃한 노드들끼리 다른 레지스터에 속해있는지 확인하면 되므로, $O(V+E)$의 계산복잡성이 듭니다. 다항시간에 풀 수 있다는 얘기입니다. 따라서 $L$은 $NP$입니다.
$L$이 $NP$-complete임을 증명해 봅시다. 그래프 컬러링(graph coloring) 문제는 이미 증명된 $NP$-complete 문제입니다. 다음과 같이 함수 $f$를 정의하면 $L$을 그래프 컬러링 문제로 바꿀 수 있습니다.
- Interfernce Graph의 노드 → Colored Graph의 노드
- Interfernce Graph의 엣지 → Colored Graph의 엣지
- Interfernce Graph의 노드에 할당된 레지스터 → Colored Graph의 노드 컬러
다음과 같이 함수 $f$를 정의하면 그래프 컬러링 문제를 $L$로 바꿀 수 있습니다.
- Colored Graph의 노드 → Interfernce Graph의 노드
- Colored Graph의 엣지 → Interfernce Graph의 엣지
- Colored Graph의 노드 컬러 → Interfernce Graph의 노드에 할당된 레지스터
위 함수 $f$의 경우 그래프의 노드와 엣지는 그대로 두고, 컬러 정보를 레지스터로 바꾸면 됩니다. 심지어 컬러를 레지스터라고 봐도 무방할 정도죠. 어쨌거나 $L$을 그래프 컬러링 문제로, 그래프 컬러링 문제를 $L$로 다항시간 내에 바꿀 수 있습니다. 따라서 $L$은 $NP$-complete입니다.
이번 글에서는 P/NP 문제에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의를 정리했음을 먼저 밝힙니다. 이 문제에 대한 개괄적인 내용은 이곳을 참고하시면 좋을 것 같습니다. 그럼 시작하겠습니다.
용어 정리
용어 및 개념 몇 가지 정리하고 넘어가겠습니다(이해를 돕기 위한 비공식적인 정의).
- Class $P$란 다항시간(polynomial time) 내에 풀리는 문제를 가리킵니다.
- Class $NP$란 운이 좋으면 다항시간에 풀리는(nondeterministic polynomial) 문제로, 어떤 답이 해당 문제의 정답인지 여부를 다항시간 내에 확인(verified)할 수 있는 문제를 가리킵니다.
- $NP$-hard란 모든 $NP$ 문제를 해당 문제로 바꿔풀 수 있을(reduce) 때 해당 문제를 가리킵니다.
- $NP$-complete란 $NP$-hard이면서 Class $NP$에 속하는 문제를 가리킵니다.
- Reducibility란 어떤 문제 $P$를 $Q$로 바꿔풀 수 있는 경우를 가리킵니다. 만일 $P$가 $Q$로 reduce할 수 있다면, $P$는 $Q$보다 해결하기가 어렵지 않다고 말할 수 있습니다.
$P$, $NP$, $NP$-complete 사이의 관계는 다음과 같습니다.
위 다이어그램을 바탕으로 다음과 같은 사실을 확인할 수 있습니다.
- $NP$ 바깥의 영역은 어떤 답이 해당 문제의 정답인지 여부를 다항시간 내에 확인할 수 없는 문제들을 가리킵니다. 다시 말해 어떤 case가 맞는지조차 알기 어려운, 미지의 문제라는 뜻입니다.
- $P≠NP$-complete입니다.
- $NP$ 문제는 다항시간 내에 풀 수 있는지 없는지 아직 모르는 문제를 가리킨다면, $NP$-complete는 절대 다항시간 내에 풀 수 없다는 게 증명된 문제를 가리킵니다.
내 알고리즘이 어떤 부류인지 판단하기
내가 만든 알고리즘 $L$이 $NP$-complete인지 아닌지 판단하는 일반적인 절차는 다음과 같습니다. 이미 알려져 있는 $NP$-complete를 지렛대 삼아 판별하는 방법입니다.
-
$L$이 $NP$임을 증명 : 내가 만든 $L$에 대한 어떤 답이 $L$의 정답인지 여부를 다항시간 내에 확인할 수 있는지를 체크
-
$L$이 $NP$-hard임을 증명
(1) 내가 만든 $L$과 가장 유사한, 이미 증명된 $NP$-complete 문제를 찾는다.
(2) $L$을 (1)에서 찾은 $NP$-complete 문제로 바꾸고, 그 역도 가능한 함수 $f$를 정의한다.
(3) (2)에서 정의한 $f$가 다항시간 내에 작동하는지를 증명한다.
판별 예시
내가 만든 알고리즘 $L$이 $NP$-complete인지 아닌지 판단하는 예시(그림 출처)를 들어보겠습니다. 레지스터 할당에 쓰이는 Interference Graph를 $L$이라고 칩시다. 이것이 $NP$-complete인지 여부를 알아내는 것이 목표입니다.
Interference Graph란 코드 시퀀스에서 둘 이상의 변수가 겹쳐 등장할 경우 엣지를 연결해두는 그래프입니다. 둘 이상의 변수를 한 레지스터에 동시에 할당하는 걸 피하기 위해서입니다.
예컨대 변수 $A$는 line 1부터 line 5까지, $B$는 line 2부터 line 3까지 살아 있어야 하고, 2~3 line에서 둘이 겹치기 때문에 Interference Graph에서 둘 사이에 엣지를 연결해 줍니다. 이렇게 만들어진 Interference Graph에서 이웃한 노드들끼리는 서로 다른 레지스터에 변수를 할당해주는 겁니다.
우선 $L$이 $NP$임을 증명해 봅시다. Interfence Graph가 주어져 있을 때, 서로 이웃한 노드들끼리 다른 레지스터에 속해있는지 확인하면 되므로, $O(V+E)$의 계산복잡성이 듭니다. 다항시간에 풀 수 있다는 얘기입니다. 따라서 $L$은 $NP$입니다.
$L$이 $NP$-complete임을 증명해 봅시다. 그래프 컬러링(graph coloring) 문제는 이미 증명된 $NP$-complete 문제입니다. 다음과 같이 함수 $f$를 정의하면 $L$을 그래프 컬러링 문제로 바꿀 수 있습니다.
- Interfernce Graph의 노드 → Colored Graph의 노드
- Interfernce Graph의 엣지 → Colored Graph의 엣지
- Interfernce Graph의 노드에 할당된 레지스터 → Colored Graph의 노드 컬러
다음과 같이 함수 $f$를 정의하면 그래프 컬러링 문제를 $L$로 바꿀 수 있습니다.
- Colored Graph의 노드 → Interfernce Graph의 노드
- Colored Graph의 엣지 → Interfernce Graph의 엣지
- Colored Graph의 노드 컬러 → Interfernce Graph의 노드에 할당된 레지스터
위 함수 $f$의 경우 그래프의 노드와 엣지는 그대로 두고, 컬러 정보를 레지스터로 바꾸면 됩니다. 심지어 컬러를 레지스터라고 봐도 무방할 정도죠. 어쨌거나 $L$을 그래프 컬러링 문제로, 그래프 컬러링 문제를 $L$로 다항시간 내에 바꿀 수 있습니다. 따라서 $L$은 $NP$-complete입니다.
Comments