P/NP 문제

1. P 문제

 

 현실적으로 쓸만한 알고리즘이라면, 그 비용이 견딜만큼 현실적인 알고리즘이라는 것이다. 알고리즘의 Time complexity가 입력 크기 n에 대해 상수 k승을 가진다면 '현실적' 이라고 본다. 예를 들어 $$O(n^2)$$ 혹은 $$O(n^3)$$등이 있다. 입력 크기가 커지면 다항으로 증가하는 비용(Polynomial Complexity)이다.

 

즉, 현실적인 비용으로 풀 수 있는 문제들, 다항(Polynomial) 알고리즘이 있는 문제들을 'P 클래스 문제' 라고 한다.

 

2. NP 문제

 

 어려운 문제의 경계에 가까이 있는 문제들의 집합을 'NP클래스 문제' 라고 한다. 운에 기대면 현실적인 비용으로 해결할 수 있는(Non-Deterministic polynomimal) 문제들이다. 

 

 운에 기대면 현실적으로 풀 수 있다는 말은 무슨 뜻인가?

예를 들어, 입구에서 출구로 이어지는 길을 찾는 '미로 찾기 문제'를 생각해보자.

잘못 선택한다면 유효한 시간 내에 출구를 찾지 못해 한참 헤매게 된다. 하지만 선택의 갈림길마다 운 좋게 늘 옳은 답을 선택했다면 시간 낭비 없이 유효한 시간 내에 미로를 탈출하게 된다. 즉, 운에 기대면 현실적인 비용으로 해결할 수 있는 문제인 것이다.

 

보다 정확히 말한다면, NP 문제인지 아닌지는 Yes/No 를 묻는 문제 중 "Yes" 라고 답하기까지만 따진다. 즉, Yes라는 답을 운에 기대어 현실적인 비용으로 할 수 있으면 NP문제라고 한다. 때문에 NP문제는 종종, "Yes"라고 답한 근거를 받아서 그 근거가 맞는지를 현실적인 비용에 확인할 수 있는 문제를 NP문제라고 한다.

 

정의를 곱씹으면 NP클래스는 P클래스를 포함한다. 운에 기대지 않고도 쉽게 풀 수 있는 문제는 운에 기대도 쉽게 풀리는 문제다. 하지만 우리가 관심있는 것은 NP클래스 문제들은 P문제가 아니고 P와의 경계 가까이 문제들이다. 아직 정답을 찾지는 못했지만 현실적인 알고리즘이 있을것만 같은 문제들...

 

다음과 같은 문제가 NP문제들이다. 

 

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

 모든 경우를 살펴볼 때 n개의 도시가 있다고 하면 모두 한 번씩 방문하는 경로의 후보들은 최대 $$n!$$만큼이다. 이 후보 경로 하나하나마다 주어진 지도에서 가능한지 살펴야하므로 Polynomial Time 으로 풀 수 있는 알고리즘은 없다.

 

 다양한 NP문제들이 있지만 생략하겠다.

 

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

 

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

 

 각설하고, 다시 NP에 대해서 설명하면,

 5 x 12 라는 문제를 풀기 위해서는 5x12를 수행해도 되지만 5를 12번 더 해도 된다. 이 말 뜻은 곱하기라는 문제를 풀기 위해서는 더하기를 할 줄 알면 해결된다는 것이다. 이런 것을 건너풀기(problem reduction) 이라고 한다.

 

 건너풀기로 NP 문제들을 모두 지배하는 하나의 문제가 있다. NP 클래스의 문제 중에 'Terminator' 역할을하는 대표적인 문제가 있는데, 이 문제만 현실적인 비용으로 풀리면 나머지 NP는 모두 이 문제로 건너풀 수 있다. 따라서 종결자 문제의 알고리즘이 다항 알고리즘이고 이 문제를 바꾸고 답을 바꾸는 비용이 다항이면 모든 NP문제도 다항 알고리즘으로 풀리는 것이다.  이런 NP에 있는 종결자 문제들을 NP-Complet문제라고 한다. 참고로 종결자 문제 역할을 하지만 NP문제인지 확인되지 않은 문제는 NP-Hard라고 한다.

 

---

출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/30/NP/