P NP 문제

P, NP, NP Complete, NP Hard 정의

---

$P$ : 어떤 문제가 주어졌을 때 다항식으로 표현되어 polynomical time 즉, 다항 시간내에 해결 가능한 알고리즘을 의미하며 알고리즘의 복잡도가 $O(n^k)$로 표현되는 문제를 '$P$'라 한다.

(복잡도 $O(n^k)$ 이하를 가지는 경우 같은 복잡도 내에 모든 해를 구한다.)

 

$NP$ : 어떤 문제가 주어졌을 때 다항식으로 표현될 수 있는지의 여부가 결정되지 않은 문제들을 'NP(Non-deterministic polynomial)'라 한다.

 

$NP-Complete$ : NP이면서 동시에 NP-Hard 에 속한다면 그 문제는 'NP-Complete'라 한다. (전수조사가 답)

 

$NP-Hard$ : 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이며, 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-Complete이므로 P와 NP는 NP-Hard의 부분집합이 되고, P≠NP인 경우는 P와 NP-Hard는 서로소가 된다.

 

*다항시간 : $T(n) = O(n^k), k$ 는 상수  => $k$가 상수로 고정이 된다면 그 문제는 해결하기 쉬운 문제. 다항시간안에 풀 수 있는 문제이므로.

 

$P = NP$ 또는 $P \neq NP$ 증명의 의의

---

$P = NP$ 또는 $P \neq NP$를 증명한다는 것은 100만 달러의 상금과 튜링상 수상 그 이상의 의미를 가진다. 만약 $P = NP$라 증명되면 현재 NP라고 일컬어지는 길찾기, 방문 판매 알고리즘 등을 포함한 모든 문제들이 전부 P 문제로서 풀릴 수 있다는 의미이다. 즉, 방문 판매와 알고리즘과 같이 무조건 시간이 오래 걸리는 방법으로 풀 수 밖에 없다 생각 되는 것 또한 방법만 찾는다면 다항 시간내에 해결할 수 있다는 것이다. 반대로 $P \neq NP$가 증명 되면, 수 많은 NP 문제들이 P 문제로 환원될 수 없음이 증명되었으니 더 쉬운 방법(P 문제로 환원할 방법)을 찾으려 더 이상 애쓸 필요가 없다는 것이다.

 

즉, 만약 우리가 이에 대한 해답을 알게된다면 지수시간(Exponential time)에 해결 가능한 모든 NP문제를 다항시간(Polynomical time)에 해결 가능한 P로 해결할 수 있기 때문에 아주 중요한 위치를 가지고 있다고 말한다.(예를 들면 암호화 알고리즘을 푸는데에 지수 시간이 걸린다. 소수를 구하는 알고리즘 또한 마찬가지이다).

복잡성 이론

---

'복잡성 이론 (Complexity Theory)' 이라는 컴퓨터 공학의 한 분야는 엄청난 계산을 필요로 하는 복잡한 문제들을 다룬다. 이것은 말 그대로 컴퓨터가 계산하는 여러 가지 문제들에 대한 '복잡성' 자체를 연구하는 분야다. 이 분야의 연구는 구체적인 알고리즘을 개발하는 것과 직접적인 상관은 없지만 어떤 문제가 쉽게 풀릴 수 잇는 문제고 어떤 문제가 쉽게 풀릴 수 없는 문제인지를 구별하도록 해주기 때문에 프로그래머들이 해결할 가능성이 없는 문제를 붙들고 시간을 허비하는 우를 범하지 않도록 해준다.

 

지수의 값이 아무리 크다고 해도 그것이 미리 정해진 상수 값이라면 그 알고리즘은 컴퓨터가 적당한 시간 안에 계산해 낼 수 있는 쉬운 알고리즘에 해당하는 것이다. 이렇게 변수위에 붙은 지수가 미리 정해진 상수인 수학 공식을 우리는 다항식 (polynomial) 이라고 부른다. 다음은 다항식의 예다.

 

$2n^3 \times n^2 -3$

 

복잡성 이론에서 다항식의 반대말은 '지수 함수 (exponential function)'다. 지수함수란 변수 위에 붙은 지수가 미리 정해져 있는 상수 값이 아니라 그 자신도 변수로 표현되는 함수를 의미한다. 다음은 지수함수의 예다

 

$2^n$ 혹은 $2n^n-1 + 2^n$

 

세일즈맨의 여행 문제를 풀기 위해 사용되는 factorial은 다음과 같은 수학 공식으로 표현되므로 다항식이라기보다는 지수함수에 속한다.

 

$n\times (n-1) \times (n-2)\times ... \times2 \times 1$

 

이 식을 모두 풀어쓰면 가장 차원이 높은 지수를 갖는 항은 맨 앞에 존재하는 n 으로 n-1 이라는 지수를 갖는다는 사실을 알 수 있다. n 의 크기가 증가하면 팩토리얼 함수 전체의 값이 엄청난 속도로 커진다. 지수함수의 특징은 바로 n 이 조금만 커지면 함수 전체의 값이 기하 급수적으로 커진다는 사실이다. 현재의 전자식 컴퓨터가 계산을 수행할수 있는 속도에는 엄연히 한계가 존재하기 때문에 계산을 수행해야 하는 양이 지나치게 커지면 컴퓨터도 계산을 수행할수 없게 된다. 이렇게 지수함수들은 n 값이 커짐에 따라서 함수의 결과가 엄청나게 빠른 속도로 증가하여 컴퓨터조차 쉽게 계산을 할 수 없기 때문에 '어려운' 문제라고 말한다. 즉 알고리즘의 속도가 다항식이 아니라 지수함수로 표현되면 그것은 어려운 알고리즘인 것이다.

 

복잡성 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 'P' 라고 부르고, 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들을 묶어서 'NP' 라고 부른다. 여기서 P 는 Polynomial (다항식) 의 머리 글자고, NP 는 nondeterministic polynomial (비결정성 다항식) 의 머리 글자를 의미한다. 이때 NP 가 non-polynomial (비다항식) 을 의미하지 않는다는 사실에 유의할 필요가 있다. 다항식이 아니라는 사실과 다항식으로 표현되는지 여부가 아직 알려지지 않았다는 사실 사이에는 엄청난 차이가 존재하기 때문이다. 다항식으로 표현되는 알고리즘은 오늘날의 컴퓨터가 적당한 시간내에 해결할 수 있는 문제기 때문에 P 에 속한 문제들은 '쉬운' 문제들이고, NP 는 그와 반대로 '어려운' 문제를 의미한다.

 

복잡성 문제를 연구하는 학자들에게 가장 어려운 질문중의 하나는 바로 "NP 에 속하는 문제들이 궁극적으로는 모두 다항식, 즉 쉬운 알고리즘을 이용해서 해결될 수 있을까?" 라는 질문이다. 만약 그렇다면 NP 에 속한 문제나 P 에 속한 문제가 모두 종국에는 다항식으로 표현되기 때문에 'P = NP' 라는 등식이 성립하게 될 것이다. 하지만 NP 에 속하는 문제가 모두 다항식으로 해결될 수 있을지 여부를 파악하거나 증명하는 것이 너무나 어렵기 때문에 이 등식은 아직도 완전하게 입증되지 않은 어려운 명제증의 하나로 통하고 있다.

 

한편 'NP-hard' 라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제들을 뜻한다. 어떤 문제가 NP 에 속하면서, 즉 다항식으로 표현될 수 있는지 여부가 알려지지 않았으면서 동시에 NP-hard 에 속한다면, 즉 '무식한 힘' 의 방법말고 다른 절묘한 알고리즘이 알려져 있지 않다면 그 문제는 'NP 완전 문제 (NP complete)' 라고 부른다. 휴, 정말 복잡하다.

 

컴퓨터 학자들과 프로그래머들은 대개 NP 완전 문제를 실용적인 관점에서 해결하기 위해서 진짜 정답을 찾기를 포기하는 대신 휠씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는데 만족한다. 이러한 알고리즘은 근사 알고리즘 (Approximation algorithm) 혹은 발견적 알고리즘 (Heuristic algorithm) 이라고 부른다. 앞서 말한 MST, 탐욕 알고리즘 (Greedy algorithm), 평면절단 방법등은 모두 이러한 알고리즘의 예인데, 실전 프로그래밍의 세계에서는 이러한 근사 알고리즘이 생각보다 많이 사용된다.

 

해밀턴 경로

---

해밀턴 경로(Hamiltonian Path)의 경우 NP-Complete에 속하는 문제로서 어떤 그래프가 주어졌을 때 모든 꼭짓점을 단 한번만 지나는 경로가 존재하는지에 대한 여부를 묻는다.

 

 

 

---

Reference

[1] http://www.aistudy.co.kr/computer/complexity_lim.htm

[2] https://wkdtjsgur100.github.io/P-NP/

[3] https://proneer.tistory.com/entry/복잡성이론-P-NP-NP-완전

[4] https://inverse90.tistory.com/entry/PNP-NP-Hard-NP-Complete