25. P-NP 문제

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

주요 내용

• 문제 난이도

• P 대 NP

• NP-완전과 NP-난해

25.1. 문제 난이도

문제의 난이도는 문제를 해결하는 알고리즘이 가질 수 있는 가장 낮은 계산 복잡도에 따라 지정된다. 즉 문제의 난이도는 해당 문제를 어떤 알고리즘도 그 난이도보다 효율적인 계산 복잡도를 가질 수 없음을 의미한다. 주어진 문제의 난이도를 계산하는 일이 일반적으로 매우 어려우며 찾지 못하는 경우도 존재한다.

예를 들어 행렬 곱셈 문제의 난이도는 \(\Omega(n^2)\)로 알려져 있다. 즉, 행렬 곱셈에 사용되는 알고리즘의 시간 복잡도는 \(\Omega(n^2)\) 보다 좋을 수 없다는 사실이 증명되었다. 하지만 지금까지 \(\Omega(n^2)\)의 시간 복잡도를 갖는 행렬 곱셈 알고리즘은 알려지지 않았다. 반면에 정렬 문제의 난이도는 \(\Omega(n \lg n)\)이며 평균 시간 복잡도가 그만큼 좋은 알고리즘이 존재한다.

Example 25.1 (행렬의 곱셈)

지금까지 알려진 가장 낮은 계산 복잡도의 알고리즘은 Josh Alman(2020)와 Virginia Vassilevska Williams(2021)이 독립적으로 발표한 알고리즘이며, 시간 복잡도가 \(O(n^{2.3728596})\)이다. 2022년 10월에 \(O(n^{2.37188})\) 의 시간 복잡도를 갖는 알고리즘이 공개되었지만 아직 완전히 검증되지는 않았다.

하지만 이와같은 알고리즘이 실전에서는 잘 사용되지 않는다. 이유는 빅-\(O\)에 숨겨진 상수 계수가 매우 크기 때문에 컴퓨터로 사실상 실행 불가능할 정도로 큰 크기의 행렬에 대해서만 의미가 있는 값이기 때문이다.

실전에서는 일반적으로 \(O(n^{2.807})\) 시간 복잡도를 갖는 슈트라센 알고리즘을 개선해서 사용한다.

이미 언급했듯이 주어진 문제의 난이도를 항상 확인할 수 있는 것은 아니다. 따라서 문제의 난이도는 일반적으로 현재까지 알려진 최선의 알고리즘의 시간 복잡도를 이용하여 분류한다.

25.1.1. 다항 시간 알고리즘

난이도 분류의 기준으로 다항 시간 계산 복잡도를 사용한다. 다항 시간polynomial time 알고리즘은 최악 시간 복잡도가 어떤 다항식 \(p(n)\)에 대해 다음이 성립하는 알고리즘이다.

\[ W(n) \in O(p(n)) \]

최악 시간 복잡도가 아래와 같은 알고리즘은 모두 다항 시간 알고리즘이다.

\[ 2n \qquad 3 n^3 + 4n \qquad 5n+n^{10} \qquad n \lg n \]

\(n\lg n\) 은 다항 함수는 아니지만 \((n\lg n < n^2)\)가 성립하기에 다항 함수로 간주한다. 반면에 최악 시간 복잡도가 아래와 같은 알고리즘은 다항 시간 알고리즘이 아니다.

\[ 2^n \qquad 2^{0.01 n} \qquad 2^{\sqrt{n}} \qquad n! \]

다항 시간 복잡도를 난이도 분류의 기준으로 사용하는 이유는 다항 시간이 아닌 알고리즘은 7.2.3절의 표에서 확인할 수 있듯이 입력값이 조금만 커져도 사실상 실행 결과를 확인할 수 없기 때문이다. 하지만 다항 시간 알고리즘이 아니더라도 경우에 따라 효율적으로 실행되는 사례가 많다. 반대로 경우에 따라 다항 시간 알고리즘을 갖는 문제가 그렇지 않은 문제보다 실제 상황에서 더 어려운 경우도 있다.

25.1.2. 난이도 분류

문제의 난이도를 일반적으로 다음 세 종류로 분류한다.

첫째, 다항 시간 알고리즘이 존재하는 문제

• 정렬된 배열을 대상으로 검색: \(\Theta(\lg n)\)

• 행렬 곱셈: \(\Theta(n^{2.3728639})\)

둘째, 다루기 힘들다고 증명된 문제

• 그래프의 모든 경로를 다 출력해야 하는 문제처럼 지수승 만큼의 출력을 요구하는 문제

• 10장에서 소개한 콜라츠 추측Collatz conjecture처럼 입력 크기에 따른 실행 시간이 전혀 알려지지 않은 문제

• 정지문제Halting problem 처럼 지수승 이상의 출력을 요구하진 않지만 다항 시간 내에 풀 수 없음이 증명된 문제

셋째, 다항 시간 알고리즘이 알려지지 않았지만 다항 시간 알고리즘이 존재하지 않는다는 증명도 없는 문제

• 0-1 배낭채우기 문제

• 외판원 문제

• m-색칠하기 문제 (m > 2)

Example 25.2 (외판원 문제)

가중치 방향 그래프가 주어졌을 때 하나의 노드(도시)에서 출발하여 다른 모든 노드(도시)를 한 번씩만 들린 후 출발 노드(도시)로 돌아오는 일주 경로 중에서 최단 경로를 찾는 문제이다.

예를 들어 아래 가중 방향 그래프에서 노드 v0 에서 출발하는 일주 경로는 세 개 존재한다.

• 일주 경로 1: v0 -> v1 -> v2 -> v3 -> v0

• 일주 경로 2: v0 -> v2 -> v1 -> v3 -> v0

• 일주 경로 3: v0 -> v2 -> v3 -> v1 -> v0

이중 마지막 경로가 최단 일주 경로이다.

외판원 문제를 해결하는 다항 시간 알고리즘은 알려지지 않았다. 동적계획법을 이용한 알고리즘의 시간 복잡도는 \(O(n^2\, 2^n)\) 이다. 여기에 더하여 \(O(n\, 2^n)\)의 공간 복잡도도 갖는다.

25.2. P 대 NP

25.2.1. 결정론적 vs. 비결정론적 튜링 기계

비결정론적 튜링 기계non-deterministic Turing machine는 특정 상황에서 그 다음 명령문을 하나가 아닌 여러 개를 동시에 실행하며 이런 과정을 하나의 해결책을 찾을 때까지 반복한다. 반면에 일반적으로 알려진, 그리고 일상적으로 사용되는 컴퓨터 프로그램의 핵심을 구현한 (결정론적) 튜링 기계는 모든 경우에서 이어지는 다음 명령문은 메모리의 상태에 따라 유일하게 결정된다.

<그림 출처: (위키피디아) Nondeterministic Turing machine>

비결정론적 알고리즘은 비결정론적 튜링 기계로 구현될 수 있는 알고리즘을 가리키며, 비결정론적 다항 시간 알고리즘은 다항 시간 계산 복잡도를 갖는 비결정론적 알고리즘이다. 반면에 일반 (결정론적) 튜링 기계로 구현될 수 있는 알고리즘은 결정론적deterministic 알고리즘이라 부른다.

25.2.2. 집합 P 와 집합 NP

비결정론적 튜링 기계는 이론적으로만 존재하며 우리가 사용하는 튜링 기계의 특성과 한계를 특징짓는 데에 유용하게 활용된다. 예를 들어 효율적인 알고리즘의 기준으로 사용되는 다항 시간 알고리즘의 한계를 밝히는 문제에서 매우 중요한 역할을 수행한다.

다항 시간 알고리즘으로 해결 가능한 모든 문제의 집합을 P로 표기한다. 예를 들어 탐색 알고리즘은 대부분 P에 포함된다. 반면에 수도쿠 문제와 외판원 문제가 집합 P에 속하는지 여부는 아직 모른다. 또한 두 문제에 대해 “다항 시간 알고리즘이 존재하지 않는다” 라는 주장 또한 아직 증명되지 않았다.

반면에 NP는 비결정론적 다항 시간 알고리즘을 갖는 문제들의 집합을 가리킨다. NP에 속하는 문제는 해당 비결정론적 알고리즘이 제시한 답이 정확한지 여부를 검증하는 데에는 다항 시간이 요구되는 문제이기도 하다. 대표적으로 수도쿠 문제가 NP에 속한다. 이유는 수도쿠 문제에 대한 답이 제시되었을 때 해당 답이 제대로 된 해답인지 여부를 판단하는 일은 곱셈과 덧셈 정도의 수준에서 다항 시간 내에 판단할 수 있기 때문이다.

<그림 출처: (유튜브)P vs. NP and the Computational Complexity Zoo>

외판원 문제와 소인수분해 문제 또한 NP에 속한다. 이유는 경로가 주어지면 주어진 시간 안에 해당 경로를 통해 모든 장소를 방문하고 되돌아올 수 있는지를 판단하거나, 어떤 수의 소인수분해 결과가 해당 수를 제대로 소인수분해 했는지 여부를 판단하는 문제는 다항 시간 내에 판단할 수 있기 때문이다.

25.2.3. P-NP 문제

P 에 속하는 문제는 모두 NP에 속한다. 이유는 결정론적 튜링 기계로 다항 시간에 실행되는 알고리즘이 제시한 답은 동일한 알고리즘을 이용하여 다항 시간 내에 정답 여부를 확인할 수 있기 때문이다. 보다 전문적으로 말하면 결정론적 튜링 기계로 구현된 알고리즘은 모두 비결정론적 튜링 기계로도 구현될 수 있다. P 와 NP가 동일한지 여부에 대해서는 아직 답을 모르며, 100만 달러의 상금이 걸린 밀레니엄 문제Millennium Problems 중에 하나다.

25.3. NP-완전과 NP-난해

문제 A를 문제 B로 변환하는 다항시간 변환 알고리즘이 존재할 때 문제 A는 문제 B로 다항시간 다대일 축소 변환가능polynomial time many-one reducible, 또는 간단하게 축소 변환 가능이라고 한다. 이는 예를 들어 문제 B를 다항 시간 내에 해결할 수 있다면 문제 A도 다항 시간 내에 해결할 수 있음의 의미한다.

다음 두 조건을 만족하는 문제 B를 NP-완전NP-complete이라 한다.

• NP에 속한다.

• NP에 속하는 임의의 다른 문제 A를 다항시간 내에 B의 문제로 축소 변환하기가 가능하다.

외판원 문제, 0-1 배낭채우기 등등 지금까지 알려진 다루기 어려운 문제 대다수가 NP-완전 문제들이다. 반면에 NP-난해NP-hard 문제는 NP-완전 문제만큼 다루기 어려운 문제를 가리킨다.

하나의 NP-완전 문제가 P에 속한다는 것이 입증되면 P = NP가 성립한다. 하지만 앞서 말한대로 P-NP 문제는 미해결 상태다. 지금까지 알려진 P, NP, NP-완전, NP-난해의 관계를 정리하면 다음 그림과 같다.

<그림 출처: (위키피디아) P versus NP problem>