P-NP 문제

캐글의 유명한 예제 중 하나인 타이타닉 문제에 대한 커널을 정리하다 NP라는 용어를 다시 접하게 되어, 다시 한 번 내용을 정리하기 위해 찾아보던 도중 이곳의 글을 읽게 되었습니다. 내용의 설명이 제가 봤던 어느 것보다 명쾌하면서 깔끔했기에 아래의 글들은 그저 다시 한 번 내 손으로 타이핑할 목적으로 정리하였습니다. 때문에 해당 링크로 가시면 가장 좋은 P-NP문제에 대한 답을 얻을 수 있을 것 같습니다.

현실적

알고리즘을 사용함에 있어서 드는 그 비용이 현실적으로 가능하다면, 그 알고리즘을 현실적인 알고리즘이라고 칭합니다. 알고리즘의 실행비용, 그러니까 복잡도가 입력 크기($ n $)에 대해 상수($ k $)승을 가진다면($ n^k $) 현실적이라고 합니다. 예를 들어, $ O(n^2) $ 혹은 $ O(n^{100}) $ 등이 그러합니다. 즉, 입력 크기가 커질수록, 비용이 다항적으로 증가(Polynomial complexity)하는 경우가 현실적인 알고리즘인 것입니다.

왜 다항이 현실적인비용일까요? 입력($ n $)에 대해 다항비용($ n^k $)을 갖는 알고리즘을 생각해봅시다. 만약 컴퓨터 성능이 $ p $배로 빨라지면 같은 입력($ n $)에 대해 비용이 $ n^k/p $로 감소할 것이며, 이는 바꿔말하면, 같은 시간 내에 더 많은 입력($ m $)을 처리할 수 있게되는 셈입니다.

실제로 계산을 해보자면, 같은 시간이라는 것은 기존 입력의 개수($ n $)에 드는 비용과 바뀐 입력($ m $)에 드는 비용이 같다는 말입니다. 즉 $ n^k = m^{k/p} $ 이며, 이에 따라 $ m = p^{1/k} $입니다.

언젠가 기계의 연산 속도는 약 2년마다 2배씩 증가한다라는 말을 들어보셨을겁니다. 위의 계산에 따라, 알고리즘 비용이 $ O(n) $이라면 2년 후에는 2배 큰 입력을 같은 시간내에 처리할 것이며, 알고리즘 비용이 $ O(n^2) $이라면 2년 후에는 $ \sqrt{2} $배 큰 입력을 같은 시간내에 처리할 것입니다.

물론 실제로 현실적으로 쓸 수 있는 비용은 다항 중에서도 $ O(n), O(n^2), O(n^3) $정도입니다. 그 이상의 차수는 아무리 다항이라도 실제로 사용하기에는 어렵습니다.

그러나 일단 다항비용으로 표현할 수 있는 알고리즘을 찾는다면(예를 들어 $ O(n^100) $), 그 문제는 대개 시간이 지나면서, 지속적인 연구를 통해 $ O(n^3), O(n^1.5),... $와 같이 개선되는 편입니다.

때문에 이런, 현실적인 비용으로 해결가능한, 다항 복잡도를 갖는 문제를 P 문제라고 합니다.

비현실적

알고리즘을 사용함에 있어서 드는 그 비용이 현실적으로 불가능하다면, 그 알고리즘을 비현실적 알고리즘이라고 칭합니다. 알고리즘의 실행비용, 그러니까 복잡도가 상수($ k $)에 대해 입력 크기($ n $)승을 가진다면($ k^n $) 비현실적이라고 합니다. 예를 들어, $ O(2^n) $ 혹은 $ O(100^n) $ 등이 그러합니다. 즉, 입력 크기가 커질수록, 비용이 기하급수적으로 증가(Exponential complexity)하느 ㄴ경우가 비현실적인 알고리즘인 것입니다.

비현실적임을 체감해봅시다. 예를 들어 $ O(n^2) $인 경우 입력 크기($ n $)이 100정도만 되어도 그 비용이 $ 2^{100} $초이며, 이는 우주의 나이($ 10^{17} ~ 10^{18} $보다도 깁니다. 실제 문제에서는 100개 이상의 입력을 다루는 문제가 많음을 생각하면, 굉장히 절망적인 비용입니다.

예를 들었을 때, 충분히 비현실적이라는 체감이 들었을 테니, 현실적 알고리즘에 대해 설명할 때 처럼 머리아픈 계산은 하지 않도록하겠습니다.

더 중요한 것은, 사실 다항비용과 기하급수비용의 분류(현실적과 비현실의 분류)는 그다지 실용적이지 못하다는 점입니다. 실제 쓸만한 알고리즘은 다항 중에서도 차수가 아주 낮은 것에 국한되어있기 때문입니다. 그럼에도 불구하고, 다항과 기하급수를 기준으로 사용하는 것의 용도는 다른 것에 있습니다. 컴퓨터로 풀기 어려운 문제가 무엇인가- 를 이해할 때입니다. 다항과 기하급수는 급이 다른 수준을 넘어 아예 다른 종류입니다. 넘을 수 없는 차원과 같습니다. 다항비용의 문제는 차수가 높더라도 언젠가 실용시킬 수 있지만, 기하급수비용의 문제는 그럴 수 없습니다. 이는 문제의 근본적인 어려움의 기준인 것입니다.

P의 경계

컴퓨터로 풀기 어려운 문제란 무엇인가? 문제가 쉽고 어렵고의 경계는 어디인가?

그 경계를 정확히 그을 수 있으면 좋습니다. 분류가 되야 문제를 효과적으로 공략할 수 있기 때문입니다. 무슨 병인지가 밝혀져야 치료법이 나오듯이, 해결가능한 문제인지 아닌지를 알고서 풀이를 도전해야하지, 증명불가능한 문제를 증명하겠다고 덤벼드는 행위를 막을 수 있습니다.

쉬운 문제는 정의하기도, 판단하기도 쉽습니다. 현실적인 비용, 그러니까 다항비용의 알고리즘을 가진다면 쉬운 문제이며, 문제에 직면했을 때, 다항 알고리즘을 만드는 것에 도전하고, 성공했다면, 쉬운문제입니다.

그러나

어려운 문제는 굉장히 난감합니다. 분명 쉬운 문제가 아닌 것이 어려운 문제임을 알고, 문제를 해결할 다항 알고리즘이 없는 것이 어려운 문제의 정의임을 알고 있습니다. 그러나 판단은 별개의 문제입니다. 다항 알고리즘이 없다는 것을 확신할 길이 막막합니다. 문제에 직면했을 때, 수없이 도전했으나 알고리즘을 찾지 못했다고 해서 해당 문제가 해결 불가능의 문제라고 확신할 수 없습니다. 바로 옆의 친구는 간단하게 해결할 수도 있으니까요.

어려운 문제를 판단하는 방법을 찾으려면 어려운 문제의 경계 가까이 가야하고, 때문에 그 경계 근처 문제들의 집합을 정의해야합니다.

주의: P와 NP는 반대의 개념이 아닙니다.

NP 집합

우리는 운에 기대면 현실적인 비용으로 해결할 수 있는(Non-deterministic polynomial) 문제들을 NP 문제라 합니다.

이 NP 문제들의 집합에는 우리가 앞서 말했던, 경계 근처의 문제들이 포함되어 있습니다. 현실적인 비용으로 풀 수 있는지가 결정나지 않은 문제들, 알려진 해결 알고리즘이라고는 기하급수의 비용을 가진 것밖에는 없는 문제들. 그러나 어쩌면, 어쩌면 다항비용으로 해결할 수 있는 문제들이 바로 경계 근처의 문제들입니다

운에 기대면 현실적인 비용으로 해결할 수 있다는 것이 무슨 뜻인가? 하면 미로찾기 문제를 생각해봅시다. 입구에서 출구로 이어지는 길을 찾아야하기에, 갈림길 마다 선택을 합니다. 잘못된 선택이 겹치면 시간이 낭비되고, 한참을 헤매게 됩니다. 하지만 매 갈림길마다, 운이 좋아 맞는 길을 선택했다면, 빠른 속도로 미로를 탈출하게 될 것입니다. 그런 운 좋은 선택을 현실적인 횟수만큼 해서 미로를 탈출할 수 있다면, 그것이 운에 기대면 현실적인 비용으로 해결할 수 있는 문제인 것입니다.

조금더 정확하게, NP 문제인지 아닌지는 예/아니오를 묻는 문제 중에서 "예(탈출로가 있긴 합니다)"라고 답하기까지만 따집니다. 즉 "예"라는 답을 운에 기대어 현실적인 비용으로 해결할 수 있다면, NP문제라고 합니다. 때문에 NP 문제를, "예"라고 답한 근거(찾은 탈출로)를 받아 그 근거가 맞는지를 현실적인 비용으로 확인할 수 있는 문제라고 설명하기도 합니다. 그러니까 답을 받아 그 답이 맞는 답인가를 현실적인 비용으로 확인할 수 있는 문제가 NP 문제라는 것입니다.

앞의 말들을 곰곰히 정리해보면 NP 집합은 모든 P 문제를 포함하게 됩니다. 운에 기대지 않고도 쉽게 풀 수 있는 문제는, 운에 기대어도 쉽게 풀리는 문제이기 때문입니다. 비행기를 타지 않아도 1시간 안에 갈 수 있는 거리는, 비행기로도 1시간 안에 갈 수 있음이 자명합니다.

그러나 계속 말하듯이, 우리가 집중해야할 문제는 P 문제가 아닌 NP 문제입니다. 아직 찾지는 못했지만, 현실적인 알고리즘이 있을 것만 같은 문제들이 바로 그것입니다.

다음은 NP 문제의 예시입니다. 흥미롭게도 우리 주변에서 흔히 접할 수 있는 문제입니다.

• 주어진 지도 위의 모든 도시들을 한 번씩만 방문하는 경로가 있을까? (해밀턴 경로 문제)

  지도에는 도시와 도시를 잇는 선이 있습니다. 이 선은 도로를 의미합니다. 출발도시를 선택한 다음, 출발도시와 연결된 다른 도시(이웃)로 이동합니다. 모든 도시를 한번씩 방문하는 경로가 있는 지도라면, 이런 선택이 모두 운 좋게 되었을 때 그런 경로를 찾을 수 있습니다. 그런 운 조은 선택은 도시의 개수만큼하면 됩니다.

  운에 기대지 않는 단순한 알고리즘은 모든 경우를 살펴보는 것입니다. 방문할 도시의 개수가 $ n $개라면, 모두 한 번씩 방문하는 경로의 후보들은 최대 $ n! $개입니다. 이 후보 경로 하나하나마다 주어진 지도에서 가능한지를 살펴야합니다.

  현재까지 다항시간 내에 푸는 알고리즘은 없습니다.

• 주어진 예산으로 주어진 지도의 도시들을 다 방문하고 돌아올 수 있을까?

  해밀턴 경로 문제의 도로에 가중치를 둔 경우입니다. 마찬가지로 NP문제이며, 현재까지 다항시간 내에 푸는 알고리즘은 없습니다.

• 주어진 부울식(Boolean formula)를 참이 되게 할 수 있을까?

  여기서 부울식은 변수와 그리고(and, *), 또는(or, +), 아닌(not, -)으로 구성된 식을 말합니다. 예를 들어, $ x * ((-x)+(-y)) $의 경우, $ x=1(True) y=0(False) $인 경우 참입니다. $ x(-x) $ 의 경우 참이 되는 경우가 없습니다.

  주어진 부울식이 $ n $개의 변수로 구성되어 있으면, $ n $개의 변수마다 0 또는 1이 가능하며, 당연히 운이 좋으면 참인 경우를 찾을 수 있으므로, NP 문제입니다.

  운에 기대지 않는 단순한 알고리즘은 모든 경우를 살펴보는 것입니다. 변수 $ n $개가 0 또는 1인 2가지 경우가 가능하므로, 전체 경우의 수는 $ 2^n $개입니다.

  현재까지 다항 시간 내에 푸는 알고리즘은 없습니다.

• 주어진 자연수를 인수분해하라.

  $ n $자리 10진수를 받습니다. 1도 아니고 자신도 아니면서 그 수를 나눌 수 있는 수가 있을까요? 만약 있기만 한다면, n번의 운좋은 선택으로 인수분해가 가능할 것입니다. 따라서 NP 문제입니다.

  운에 기대지 않는 단순한 알고리즘은 모든 경우를 살펴보는 것입니다. 받은 자연수보다 작은 자연수를 2부터 시작하여 하나하나 받은 자연수를 나눌 수 있는지 체크합니다. $ n $자리 10진수이므로 최대 $ 10^n -1 $개 경우를 가집니다.

• 1000만 관객을 넘기는 영화를 제작하라. 제작 중 $ n $번 디자인 선택을 해야한다.

  매번 디자인 선택(시나리오 작성, 배우 캐스팅, 촬영, 편집 등을 포함) 때마다 올바른 방향으로 해 간다면 만들 수 있습니다. 운이 좋다면 $ n $번의 선택을 잘 하면 될 것입니다.. NP 문제입니다.

  운에 기대지 않는다면 비현실적인 비용이 필요합니다. 매번 마주치는 디자인 후보의 가짓수가 2개뿐일지라도, 만들 수 있는 영화의 가짓수는 $ 2^n $이며 당연히 이를 아득히 뛰어넘는 가짓수가 생길 것입니다.

이런 NP 문제들은 곤혹스럽습니다. 주변에 흔히 만나는 문제들인데 현실적인 비용으로 정확한 답을 내는 알고리즘은 아직 없다니.

그러나 아이러니하게도, 이런 NP 문제들은 그렇기 때문에 유용합니다. 디지털 암호 기술을 버티는 기둥이 이런 NP 문제들이기 때문입니다. 보통 보안을 위해 이런 NP 문제들이 쓰입니다. 암호화된 메시지를 도청한 사람이 암호를 풀기 위해서는 이런 NP 문제들을 풀어야하게끔 만든 것입니다.

아무튼, 어려운 문제가 무엇인지 판단하는 방법을 컴퓨터 사이언스에서는 어떻게 찾아가는지에 대해 계속해서 정리해보겠습니다. 다시한번, 우리는 NP 집합의 문제들로 어려운 문제와 쉬운 문제의 경계를 찾아나가고 있습니다.

P != NP ...?

P와 NP가 같은가 다른가에 대한 문제는 그 누구도 답하지 못하였습니다. 그러니 대부분의 현대 과학자들은 아마도 P != NP일 것이라 생각하고 있습니다. 만약 P = NP라면, 위의 예시에 있는 명작 영화를, 현실적인 비용으로 컴퓨터가 자동 생산할 수 있다는 말이 될 것인데, 이는 꽤나 거북합니다.

P의 바깥

P != NP가 사실이라면, P가 아닌 NP 문제들이 있다는 것입니다. 그런 문제는 P가 아니므로 어려운 문제라 말할 수 있고, 그렇다면, 어떤 문제가 P가 아닌 NP 문제인가(P의 바깥인가)를 판단해야합니다.

한 방법이 겨우 있습니다. 겨우라는 표현을 쓴 것은, 그 방법이 믿을 만하지만, 완전하지는 않기 때문입니다. 모든 P 바깥의 문제가 그 방법으로 확인되는 것은 아닙니다. 그 방법을 통과하면, P 바깥의 문제인 것은 확실하지만, 통과하지 못했음에도 P 바깥의 문제인 경우가 있기 때문입니다.

그 방법은 NP 집합의 재미있는 성질때문에 가능합니다. 그 성질은, NP 문제 중에서도 가장 어려운 문제가 있다는 것입니다. 때문에 모든 NP 문제는 이 문제보다 어려울 수 없고(무조건 더 쉽고), 따라서 이 문제는 당연히 P 바깥입니다. 즉 내가 직면한 어떤 문제(A)가 가장 어려운 문제(B)만큼 어렵다면 그 문제(A)는 분명 P 바깥인 것입니다. 이 사실을 발견하는 데에는 건너풀기(Problem reduction)라는 개념이 사용됩니다.

건너풀기(Problem reduction)

NP로 분류한 문제들은 모두 단단히 연대해있습니다. 달라 보이지만 사실은 한 덩어리로 묶여있는 것이지요. 어려운 문제와 쉬운 문제의 경계에 위치해있기 때문입니다.

이런 연대가 건너풀기라는 개념으로 확인됩니다. 건너풀기란 이런 것입니다.

문제 A를 풀어야한다. 건너편 문제 B를 풀고, 그 알고리즘을 이용해 A를 풀 수 있다. 문제 A를 푸는데 문제 B로 건너 푼 것이다. 즉 간접적으로 푼 것이다. 단, 문제 B로 푼 답을 문제 A의 답으로 옮기는 과정은 다항 비용으로 처리될 수 있어야 한다.

건너풀기는 일상에서 흔한 일입니다. 예를 들면 곱하기를 더하기로 건너 풀 수 있습니다. 즉 $ 5 * 2 $는 $ 5 $를 $ 12 $번 더하는 것으로 해결됩니다.

건너풀기로 모든 NP 문제들을 지배하는 하나의 문제가 있습니다.NP 문제 중 종결자 역활을 하는 대표적인 문제가 있다는 것입니다. 이 문제만 현실적인 비용으로 해결하면, 나머지 NP 문제들은 모두 이 문제로 건너 풀 수 있습니다. 모든 NP 문제를 종결자 문제로 건너풀기할 수 있다는 뜻입니다. 따라서 이 종결자 문제만 다항 알고리즘으로 푼다면, 모든 NP 문제를 다항 알고리즘으로 풀 수 있게 되는 것입니다.

이러한 종결자 문제를 우리는 NP 완전(Complete) 문제라고 합니다. 모든 NP 문제를 NP 완전 문제를 통해 건너풀 수 있기 때문입니다. 이는 동시에 NP 문제 중 가장 어려운 문제입니다.

컴퓨터 사이언스에서 완전이라는 단어가 종종 나옵니다. 빠뜨림이 없다라는 뜻입니다. 그래서 NP 완전입니다. 참고로 종결자 역활은 하지만, NP 문제인지 확인되지 않은 문제는 NP 하드(Hard) 문제라고 합니다.

위의 NP 문제 예시들이었던 해밀턴 경로 문제, 부울식 판별 문제 등이 사실 NP 완전 문제입니다. (즉 NP 완전 문제는 유니크한 문제가 아닙니다.)

어려운 문제인지 판단하기

이제 이 NP 완전 문제를 어려운 문제를 판별하는 기준으로 사용할 수 있게 되었습니다. 앞서 말한 것처럼, 문제가 어렵다라는 것은 P가 아니다라는 것이며, P != NP를 가정한다면, 주어진 문제가 적어도 NP 완전 만큼 어렵다면, 그 문제는 P 바깥의 문제, 즉 어려운 문제가 되는 것입니다.

그래서 어떤 문제를 만났을 때, 다항 알고리즘을 찾지 못하고 있다면, 그자체가 NP 완전인지, 또는 NP 완전 만큼 어려운 문제인지를 건너풀기를 활용해 확인해야합니다. 사실이라면 적어도, 그 문제는 NP 완전 문제만큼 어려운 문제이며, P 바깥의 문제가 확실시되는 것입니다.