본문 바로가기

학습컨텐츠/계산 이론

P vs NP (2) - 문제의 환원과 NP-완전성으로의 응용

0. 간단한 복습


먼저 P와 NP에 대한 간단한 복습으로부터 시작하자.

P 문제는 '결정성 알고리즘으로 다항식 시간 내에 해결 가능결정형 문제'이다. '결정성 알고리즘', '다항식 시간', '해결 가능하다', '결정형 문제'와 같은 용어들은 모두 이미 친숙하리라고 가정하고 앞으로 설명할 것이다. P 문제들의 집합을 P 클래스라 한다.

NP 문제는 '비결정성 알고리즘으로 다항식 시간 내에 해결 가능결정형 문제'이다. P 문제와 다른 점이라면 알고리즘이 결정성이냐 비결정성이냐의 차이이다. NP 문제들을 집합을 NP 클래스라 한다.

결정성 알고리즘은 비결정성 알고리즘에서 비결정도가 1인 특수한 경우이다. 그러므로 P 클래스가 NP 클래스에 포함됨은 명백하다.

역으로 NP클래스가 P클래스에 포함되는지는 아직 증명도 반증도 되지 않았다. 이것을 P : NP문제라고 한다. 이 문제가 정보 과학에서 어떤 의의를 가지는 지는 P vs NP 컨텐츠의 마지막 절을 참고하자.

P : NP 문제에 보다 가까이 접근하기 위해 도입된 개념이 NP-완전성이다. 이 컨텐츠에서는 전편에서 간략하게 소개하는데 그쳤던 '환원'을 보다 심층적으로 다루고, 이를 이용하여 어떤 문제가 NP-완전 문제임을 증명하는 방법에 대해 배워볼 것이다.




1. 환원


환원reduction이란 간단히 말해 한 문제를 이용하여 다른 문제를 푸는 것을 뜻한다. 다음은 환원의 아주 간단한 예로 주어진 수의 제곱을 계산하는 문제 square가 주어진 두 수를 곱하는 문제 multiply로 환원된 것이다.

  # 예제 1

def multiply(x,y):

    return x*y


def square(x):

    return multiply(x,x)


우리는 P와 NP 문제를 다루고 있기 때문에, 결정형 문제에 한해서만 환원을 논할 것이다. 두 결정형 문제 AB에 대해 다음이 성립할 때, 'AB로 환원된다' 고 정의한다.

알고리즘 f가 존재하여, 문제 A의 모든 입력 x에 대해

          (1) f는 출력 f(x)를 내놓고 정지한다.

          (2) A(x) = B(f(x))가 성립한다.


위 그림은 문제 A가 알고리즘 f 통해 문제 B로 환원된 것을 도식화 한 것이다.

다음 예는 주어진 정수가 5의 배수인지를 판별하는 문제 isMultipleOfFive를 주어진 정수가 10의 배수인지를 판별하는 문제 isMultipleOfTen으로 환원시킨 것이다. 이때 f는 단순히 주어진 수의 두 배를 출력하는 함수가 된다. 일반적으로 알고리즘 f의 역할은 문제 AB의 입력을 맞추어주는 것이다.

# 예제 2

def f(x):

    return 2*x


def isMultipleOfFive(x):

    return isMultipleOfTen(f(x))


환원은 어떤 의미를 갖는가? 문제 A가 문제 B로 환원된다는 것은 어떤 관점에서 보면 문제 B가 문제 A보다 더 어렵다는 것으로 해석할 수 있다. 왜냐하면 AB로 환원된다면, 문제 B를 풀 경우 A까지 덩달아 풀리는 셈이기 때문이다. 반대로 A가 풀렸다고 해도 B를 풀 수 있는지는 보장할 수 없다. 예제1에서처럼 문제 A가 문제 B의 특수한 경우일 때를 생각하면 이해가 쉬울 것이다.

  • 문제 A가 문제 B로 환원된다.
  • 문제 B가 문제 A보다 더 어렵다.
  • 문제 B를 풀 수 있으면 문제 A도 풀 수 있다.


특별히 f 다항식 시간 알고리즘인 경우, 이를 다항식 시간 환원polynomial-time reduction이라 한다. 다항식 시간 환원은 P와 NP의 관계에서 중요한 연결고리 역할을 한다.




2. NP-완전성


다음이 성립할 때, 결정형 문제 XNP-어렵다NP-hard고 정의한다.

임의의 NP 문제가 X다항식 시간 환원된다.


따라서 어떤 문제가 NP-어렵다는 것은 '그것이 모든 NP 문제보다 어렵다' 혹은 '그 문제를 풀면 모든 NP 문제를 풀 수 있다'는 것을 의미한다. 나아가 단순한 환원이 아니고 다항식 시간 환원이기 때문에 우리는 더 많은 정보를 얻을 수 있다. 다음 정리를 보자.


정리. 만약 NP-어려운 문제 하나가 P 문제라면, P 클래스 NP 클래스이다.

증명은 간단하다. 이 문제를 B라 하자. 정리의 조건에서 B가 P 문제라 하였으므로, 이것을 입력의 크기 대한 다항식 시간 이내로 풀 수 있는 알고리즘이 존재한다.

이제 임의의 NP 문제 A를 생각하자. B가 NP-완전이므로 다항식 시간 알고리즘 f가 존재하여, A f를 통해 B로 환원된다. 이때에도 역시 알고리즘 f의 시간복잡도가 다항식 보다 작아지도록 둘 수 있다.

우리는 A(x) = B(f(x))임을 이용하여 A를 풀 것이다. 임의의 입력 x 에 대해 그것의 크기를 이라 하면 f(x)의 크기는 이하가 된다. 따라서 f(x)으로부터 B(f(x))를 계산하는데 걸리는 시간은 이하이다. 그러므로 A(x)를 계산하는데 걸리는 총 시간은 보다 작고 이것은 다항식이므로 A 는 P 문제이다.

모든 NP 문제가 P 문제임을 보였으므로, P 클래스 NP 클래스라는 결론을 얻는다.



다음이 성립할 때, 어떤 결정형 문제가 NP-완전이다NP-complete 고 정의한다.

(1) NP 문제이다.

(2) NP-어려운 문제이다.


어떤 문제가 NP-완전이라면 그것은 다른 모든 NP 문제보다 어려운 NP 문제인 것이다. 그렇다고 해서 NP-완전 문제가 꼭 하나만 있어야 한다는 법은 없다. 두 문제가 서로에게 환원될 수도 있기 때문이다.

앞의 정리에 의해 P : NP 문제를 풀 수 있는 한가지 가능성이 생겼다. NP-완전 문제 중에서 단 하나라도 P 클래스에 속하는 것을 찾으면, NP 클래스와 P 클래스가 똑같다는 것이 보여지는 것이다.

그 대우 명제 역시 흥미롭다. 만약 P 클래스와 NP 클래스가 다르다는 것이 증명되면, NP-완전 문제들에 대해서는 다항식 시간 결정성 알고리즘이 존재하지 않음이 밝혀지는 것이다.

그렇다면 어떤 문제가 NP-완전 문제라는 것은 어떻게 알 수 있을까? 다음 정리를 보자.


정리. A가 NP-완전 문제이고 B가 NP 문제일 때, 만약 AB로 다항식 시간 환원된다면, B는 NP-완전 문제이다.


증명은 앞에서 한 것과 유사하므로 생략한다. 주어진 조건으로부터 모든 NP 문제가 B로 다항식 시간 환원됨을 보여주면 된다.

다음 절에서는 위 정리를 사용하여 어떤 문제가 NP-완전임을 보이는 방법을 구체적인 예를 통해 알아보자.




3. 응용: 어떤 문제가 NP-완전임을 증명하기


3.1. 충족 가능성 문제 (SAT)


SAT 는 충족 가능성 문제Boolean satisfiability problem의 약어이다. 프로그래밍을 하다 보면 다음과 같은 논리식을 많이 볼 수 있다. 각 알파벳은 변수이고, 는 AND, 는 OR, 는 NOT을 뜻한다.

(1)

(2)

(1)의 경우, 를 참으로 주면, 나머지 변수들의 값에 관계없이 전체 식의 논리값은 참이 된다. 그러나 (2)의 경우에는, 변수를 어떻게 대입하는지에 관계없이 항상 전체 식의 논리값은 거짓이 된다. (1)과 같이 전체 논리값을 참으로 만드는 대입이 존재할 때, 그 논리식이 충족 가능하다satisfiable고 말한다. SAT는 변수, , , , 괄호로 이루어진 논리식을 입력으로 받아, 그것의 충족 가능성 여부를 출력하는 문제이다.


문제: 충족 가능성 문제 (SAT)

입력: 변수, , , , 괄호로 이루어진 논리식

출력: 입력이 충족 가능하면 True, 그렇지 않으면 False


SAT가 NP 문제임은 쉽게 알 수 있다.

# 예제: SAT 문제에 대한 다항식 시간 비결정성 알고리즘

def SAT(E):

   V = L(E) # V 논리식 E 포함된 변수들의 리스트로 만듦

   for i in range(len(V)): # 변수를 혹은 거짓으로 설정

       V[i] = True OR V[i] = False

   return T(E,V) # 위의 대입에 대한 전체 식의 논리값을 출력


위의 코드에서 LT는 모두 P문제이다. 그리고 알고리즘에 비결정성을 주는 부분인 for문도 선형 (입력의 크기에 대한 1차 다항식) 시간 내에 해결 가능하다.

1971년 SAT가 NP완전 문제임이 증명되었다. 이 정리를 최초로 증명한 사람의 이름을 따 쿡의 정리Cook's theorem라고 한다. 증명은 어려우므로 생략한다.


쿡의 정리. SAT 문제는 NP-완전 문제이다.


이후 수많은 NP문제들이 SAT 문제로부터의 다항식 시간 환원을 통해 NP-완전임이 증명되었다. 앞으로 보게 될 문제들 간의 관계가 아래 그림에 나타나있다. 그림에서 두 문제가 화살표로 와 같이 연결된 것은 로 다항식 시간 환원됨을 뜻한다.



3.2. CSAT와 k-SAT


논리식들 중에서 논리곱 정규형conjunctive normal form 혹은 짧게 CNF라 불리는 것들이 있다. 하나의 CNF는 여러 개 절clause의 논리곱(AND)로 이루어져 있고, 각 절은 여러 개 단위식literal의 논리합(OR)으로 이루어져 있다. 각 단위식은 하나의 변수() 혹은 그 역()이다. 다음은 CNF의 예시이다.

CNF 중에서 각 절이 정확히 k개 단위식의 논리합으로 표현된 경우를 k-CNF라고 한다. 다음은 3-CNF의 예시이다.

이로부터 다음의 두 문제가 정의된다.


문제: CNF의 충족 가능성 문제 (CSAT)

입력: 변수, , , , 괄호로 이루어진 CNF

출력: 입력이 충족 가능하면 True, 그렇지 않으면 False


문제: k-CNF의 충족 가능성 문제 (k-SAT)

입력: 변수, , , , 괄호로 이루어진 k-CNF

출력: 입력이 충족 가능하면 True, 그렇지 않으면 False


CSATk-SAT는 모두 SAT의 특수한 경우들이다. 즉 SAT보다 쉬운 문제들이다. 하지만 SAT는 CSAT로 다항식 시간 환원된다. (증명은 생략한다.) 따라서 7쪽의 정리에 의해 CSAT는 NP-완전 문제이다.

k-SAT는 k의 값에 따라 문제의 어려움이 달라진다. k가 1 혹은 2인 경우엔 P 문제이다. 반면, 3-SAT부터는 NP-완전 문제임이 밝혀져 있다. (증명은 역시 어려우므로 생략한다.)



3.3. 독립 집합 문제 (IS)


유한 개의 꼭지점vertex과 꼭지점들 사이의 모서리edge로 이루어진 자료 구조를 그래프graph라고 한다. 꼭지점의 집합을 , 모서리의 집합을 라 하였을 때 그래프는 그 둘의 순서쌍 으로 나타낼 수 있다. 그래프를 이루는 모서리의 방향성 여부에 따라 무향 그래프undirected graph유향 그래프directed graph로 분류하기도 한다. 아래 그림에서 왼쪽은 무향 그래프이고, 오른쪽은 유향 그래프이다.



무향 그래프가 주어졌을 때, 서로를 직접 연결하고 있는 모서리가 하나도 없는 꼭지점들의 집합을 독립 집합independent set이라고 한다. 아래 그래프에서 은 독립 집합이다. 는 1과 2가 연결되어 있으므로 독립 집합이 아니다.



독립 집합 문제는 다음과 같이 정의된다.

문제: 독립 집합 문제 (IS)

입력: 무향 그래프 , 자연수

출력: 원소가 이상인 독립 집합이 존재하면 True,

          그렇지 않으면 False


IS가 NP 클래스에 속한다는 것 정도는 굳이 따로 보여주지 않아도 느낌이 올 것이다. 비결정성 알고리즘으로 임의의 개 꼭지점을 선택한 뒤, 그것들이 독립 집합을 이루는지 여부만 결정하면 된다. 주어진 집합이 독립 집합인지 판단하는 것은 P 문제이다. 이유는 어렵지 않으니 각자 생각해보자.

이제 IS가 NP-완전임을 보이기 위해 3-SAT를 IS로 환원시킬 것이다. 3-CNF 꼴의 논리식 x가 주어졌을 때, 3-SAT(x) = IS(f(x))가 되는 다항식 시간 알고리즘 f를 만들어보자.

먼저 주어진 논리식을 이루는 단위식들을 각각 그래프의 꼭지점으로 설정한다. 이때 같은 단위식이 여러 절에 중복해서 나와도 각각 다른 꼭지점으로 취급해주어야 한다. 여기서 다음의 두 가지 규칙에 따라 모서리를 만들어주면, 그래프가 완성된다.

(1) 각 변수()와 그 역()을 모서리로 연결한다.

(2) 같은 절 안에 있는 단위식들끼리 모서리로 연결한다.


위 규칙에 따르면, 논리식 
이 주어졌을 때, 다음 그래프가 생성된다. 각 단위식이 어느 절에 속한 것인지를 표현하기 위해 아래 첨자를 붙였다. 여기서 빨간색 모서리는 규칙 (1)에 의해 만들어진 것이고, 파란색 모서리는 규칙 (2)에 의해 만들어진 것이다.

그러면 자연수 는 어떻게 두어야 할까? 바로 논리식을 구성하는 절의 개수이다. 이 경우는 가 될 것이다. 요약하면 알고리즘 f가 하는 일은 다음과 같다.


f: 3-SAT를 IS로 환원시켜주는 알고리즘

입력: 3-CNF

출력: 위 규칙에 따라 만들어진 무향 그래프 , 절의 개수


이제 정말로 3-SAT(x) = IS(f(x))가 성립하는지 확인할 차례이다. 위의 예를 보자.

하나의 CNF는 여러 개 절의 논리곱이기 때문에, 논리식 가 참이 되기 위해서는 각각의 절 가 모두 참이어야 한다. 그리고 하나의 절은 여러 개 단위식의 논리합이기 때문에, 절 가 참이 되기 위해서는 단위식 , , 셋 중의 하나가 참이어야 한다. 마찬가지로 가 참이 되기 위해서는 단위식 , , 셋 중의 하나가 참이어야 한다.

따라서 , , 중의 하나, , , 중의 하나 이렇게 두 개의 단위식을 선택하여 거기에 참을 대입하면, 전체 식의 논리값이 참이 되는 것이다. 물론 이게 항상 가능하지는 않다. 왜냐하면 변수 와 그 역 에 동시에 참을 대입하는 것은 불가능하기 때문이다.

이것은 주어진 논리식과 대응되는 그래프에서 개 짜리 독립 집합을 찾는 것과 정확히 같은 문제이다. 같은 절에 있는 단위식끼리는 파란색 모서리로 연결되어 있기 때문에 개 꼭지점으로 구성된 독립 집합은 항상 각 절에서 단위식 하나씩을 선택해 놓은 것이 된다. 또한 각 변수와 그 역은 빨간색 모서리로 연결되어 있기 때문에 이 둘을 같이 선택하는 것은 불가능하다.

그러므로 만약 우리가 그래프에서 꼭지점 개의 독립 집합을 찾으면, 그 단위식들을 참으로 두는 것이 주어진 논리식을 충족시키는 대입이 된다. 위 예의 경우 꼭지점 2개로 구성된 독립 집합 가 존재한다. 따라서 논리식 은 충족 가능하다.



3.4. 꼭지점 덮개 문제 (VC)


무향 그래프가 주어졌을 때, 임의의 모서리에 대해 그것의 양 끝점 중 적어도 하나를 포함하고 있는 꼭지점들의 집합을 꼭지점 덮개vertex cover라고 한다. 아래 그래프에서 은 꼭지점 덮개이다. 는 4와 6을 잇는 모서리의 양 끝점을 둘 다 포함하기 있지 않으므로 꼭지점 덮개가 아니다.



꼭지점 덮개 문제는 다음과 같이 정의된다. 이 문제 또한 NP 문제이다.

문제: 꼭지점 덮개 문제 (VC)

입력: 무향 그래프 , 자연수

출력: 원소가 이하인 꼭지점 덮개가 존재하면 True,

그렇지 않으면 False


VC는 IS로부터의 다항식 시간 환원을 통해 NP-완전임을 증명한다. 아래 알고리즘에 대해 IS(x) = VC(f(x))가 성립하는 이유는 의 부분집합 이 독립 집합인 것과 그 여집합 이 꼭지점 덮개인 것이 동치이기 때문이다. 이유는 각자 생각해보자.

f: IS를 VC로 환원시켜주는 알고리즘

입력: 무향 그래프 , 자연수

출력: 무향 그래프 , 자연수 (, 즉 에서 꼭지점의 개수)



3.5. 해밀턴 회로 문제 (HC)


그래프가 주어졌을 때, 한 꼭지점에서 출발하여 모서리를 따라 움직이면서 각 꼭지점을 정확히 한번씩 방문하고 다시 처음의 꼭지점으로 돌아오는 방법이 존재할 때 그 경로를 해밀턴 회로Hamiltonian circuit라고 한다. 아래 그림의 각 그래프에서 빨간색으로 표시된 경로가 해밀턴 회로이다.



그래프가 무향 그래프인 경우와 유향 그래프인 경우 각각에 대해 다음의 두 문제가 정의된다.

문제: 유향 해밀턴 회로 문제 (DHC)

입력: 유향 그래프

출력: 에 해밀턴 회로가 존재하True, 그렇지 않으면 False


문제: 해밀턴 회로 문제 (HC)

입력: 무향 그래프

출력: 에 해밀턴 회로가 존재하True, 그렇지 않으면 False


DHC와 HC는 모두 NP 문제이다. 9쪽의 그림에서 알 수 있듯이, 3-SAT는 DHC로 다항식 시간 환원되고, DHC는 HC로 다항식 시간 환원된다. (증명은 생략한다.) 따라서 DHC와 HC는 모두 NP-완전 문제이다.



3.6. 외판원 문제 (TSP)


각 모서리에 가중치 혹은 무게weight가 주어진 무향 그래프가 있다고 하자. 여기서 그래프의 꼭지점을 도시로, 모서리를 도시들 사이의 교통수단으로, 그리고 모서리의 가중치를 교통수단을 이용하는데 드는 비용으로 바꾸어 생각할 수 있다.

이런 상황에서 만약 여러분이 외판원이고 얼마만큼의 예산이 주어졌다 하였을 때, 그 한도 내에서 각 도시를 정확히 한번씩 방문하고 처음 출발한 곳으로 돌아오는 것이 가능할까? 이것이 바로 그 유명한 외판원 문제traveling salesman problem이다. 아래 그림에서 A, C, B, D를 차례로 거쳐 다시 A로 돌아오는 경로는 총 비용이 이다.

문제: 순회 세일즈맨 문제 (TSP)

입력: 모서리에 가중치가 있는 무향 그래프 , 예산

출력: 비용이 이하인 해밀턴 회로가 존재하True, 그렇지 않으면 False


TSP는 HC로부터의 다항식 시간 환원을 통해 NP-완전임을 증명한다. 아래 알고리즘에서 HC(x) = TSP(f(x))가 성립하는 이유는 각자 생각해보자.


f: HC를 TSP로 환원시켜주는 알고리즘

입력: 무향 그래프

출력: 에서 모든 모서리의 가중치를 1로 준 무향 그래프 , 자연수




4. 정리


지금까지 환원을 이용하여 어떤 문제가 NP-완전이라는 것을 보이는 방법에 대해 알아보았다. 인터넷에서 검색을 해보면 이 외에도 수많은 NP-완전 문제에 대한 정보를 얻을 수 있다.

Microsoft Windows에서 제공하는 지뢰찾기 게임 역시 NP-완전 문제임이 2000년에 증명되었다고 한다. 구체적으로는 지뢰찾기 게임 판이 주어졌을 때 그것을 만족시키는 지뢰의 배치가 존재하는지 여부를 결정하는 문제이다. 아래 왼쪽 그림은 존재하는 경우이고, 아래 오른쪽 그림은 존재하지 않는 경우이다.

         

이처럼 NP-완전 문제는 책 속에만 있는 것이 아니다. 여러분도 주변에서 발생하는 이런저런 문제들을 아무 생각 없이 지나치지 말고 '혹시 이것도 NP-완전 문제가 아닐까?'하고 눈여겨 보는 습관을 들이는 것을 어떨까? 거기서 위대한 발견이 나올지 누가 알겠는가!