[펌글]NP-complete 문제에 대한 쉬운 정리

P, NP, NP-완전

알고리즘을 공부해본 사람이라면 누구나 들어보았을 말이다. 용어의 정의자체도 난해하지만 그것에 대한 풀이 또한 쉽게 풀이해논 내용이 없어 한참을 읽어봐도 이해가 되지 않았다. 혹, 이해를 해도 시간이 지나면 그들간의 차이점을 생각해 내는 것이 쉽지 않았다.

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

이러한 복잡성 이론의 하나인 P, NP를 이해하는데 필요한 용어부터 알아보자. 결정문제(decision problem)라는 것이 존재한다. 결정문제는 단어 그대로 '예', '아니오'로 결정해야만 하는 문제이다. 흔히 국회 청문회의 경우 청문 대상자를 놓고 하는 질문들 같은 경우이다. 그들은 다른 답변보다 예인지 아닌지를 듣고 싶어하기 때문이다.

질문 : 000 사실이 있습니까? 예, 아니오로만 답변하세요.
답변 : 그게 ...

그들은 결정문제가 아닌 문제들도 결정문제로 만드는 경우가 있다. 하지만 알고리즘에서는 결정문제는 모든 입력으로부터 {예, 아니오}로의 매핑이 가능해야 한다. 우리가 살펴본 P와 NP는 모두 이러한 결정문제에 속한다.

어떤 문제를 분석할 때 n이라는 변수에 붙은 지수가 1이나 2처럼 미리 정해진 값, 즉 상수(constant)로 표현되는 경우 그 문제를 '쉬운(tractable)'문제라고 한다. 지수의 값이 아무리 크다고 해도 그것이 미리 정해진 상수 값이라면 그 알고리즘은 컴퓨터가 적당한 시간 안에 계산해 낼 수 있는 쉬운 알고리즘에 해당하는 것이다. 이렇게 변수위에 붙은 지수가 미리 정해진 상수인 수학 공식을 우리는 (중, 고등학교에서 수학에서 이미 배운 바와 같이) 다항식 (polynomial) 이라고 부른다. 다음은 다항식의 예다.

2n     3n³ + 4n    5n + n¹⁰    nlg n

nlg n은 다항식은 아니지만 nlg n  < n² 의 부등식이 성립하므로 n에 대한 다항식보다 작으므로 앞서 정의한 쉬운문제에 분류될 수 있다.

이에 반해, 다항식으로 풀 수 없는 문제들이 있다. 복잡성 이론에서 다항식의 반대는 지수함수이다(고등학교 수학에서는 지수함수의 반대말은 로그함수였다). 지수함수란 변수 위에 붙은 지수가 미리 정해져 있는 상수 값이 아니라 그 자신도 변수로 표현되는 함수를 의미한다. 다음은 지수함수의 예다.

-2ⁿ     2^0.01n    2^n-1    n!

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

복잡성 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 '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), 평면절단 방법등은 모두 이러한 알고리즘의 예인데, 실전 프로그래밍의 세계에서는 이러한 근사 알고리즘이 생각보다 많이 사용된다.

이러한 NP 완전 문제에 속하는 문제는 많다. 비밀번호를 깨뜨리기 위한 해킹 과정도 말하자면 이러한 NP 완전 문제에 속한다고 볼 수 있다. 비밀번호를 찾아내기 위한 알고리즘으로는 세일즈맨의 여행 문제에서처럼 문자를 하나씩 대입해 보는 것 말고는 다른 뾰족한 방법이 없기 때문이다. 그렇지만 이렇게 문자를 대입하는 경우에 시도해봐야 하는 경우의 수가 너무나 많기 때문에 이러한 방식으로 비밀번호를 찾아내는 것은 현실적으로 어렵다. 그러나 이론과 현실 사이에는 항상 간극이 존재하기 마련이다. 이론적으로 보았을 때 비밀번호를 깨뜨리는 문제는 NP 완전 문제에 속하도록 되어 있지만 현실은 그렇지 않기 때문에 문제가 발생한다.


Reference : 복잡성이론 : 임백준

원본: http://proneer.tistory.com/entry/%EB%B3%B5%EC%9E%A1%EC%84%B1%EC%9D%B4%EB%A1%A0-P-NP-NP-%EC%99%84%EC%A0%84