P - NP 문제

안녕하세요. 언제나 휴일, 언휴예요.
이번에는 NP 완전(NP - Completeness) 이론에 관해 소개할게요.

1971년 스티븐 쿡(Steven Cook)과 1972년 리처드 카프(Richard Karp)는 논문을 통해 P-NP 문제를 꺼내들었죠.

P는 Polynominal(다항) 시간에 문제를 풀수 있는 문제를 말해요.
n 개의 자료가 있을 때 문제를 해결하는데 걸리는 시간을 n의 다항식(1, n, n^2 등)으로 표현할 수 있는 문제예요.
예를 들어 버블 정렬 알고리즘은 점근식 표기 O(n^2)으로 표현할 수 있어서 P 문제죠.
이와 같은 문제는 전산학에서 풀기 쉬운 문제 혹은 컴퓨터로 계산할 수 있는 문제라고 말합니다.

NP는 문제 해결 방법을 찾는 것은 어렵지만 답을 제시했을 때 맞는지 틀리지를 판별하는 것은 쉬운 문제를 말해요.
헤밀턴 경로 문제나 외판원 문제, 배낭 채우기 문제 등이 있어요.
대부분 경우의 수를 전부 확인하면서 문제를 푸는 방법으로 해결하는 문제들이죠.

하지만 수학적으로 NP문제는 P문제를 포함한다고 증명하였답니다.

아이러니하게도 NP의 여집합인 여NP에도 Pㅜ문제를 포함한다고 증명을 하였죠.

수학적 관점에서는 논리적 모순을 없애기 위한 노력을 많이하죠.

저는 실용적인 관점에서 NP는 해결 방법은 어렵지만 답을 제시하면 맞는지 틀린지 판별하기 쉬운 문제라고 말합니다.

논리적 모순이 있다고 여길 수 있지만 모순이 있다고 쓸모없는 것은 아니며 개인적인 판단에 의해 이처럼 말하고 있어요.

배낭 채우기 문제
배낭과 여러 종류의 물건들이 있습니다. 물건마다 무게와 가치를 알고 있어요.
배낭에 A 무게 이상을 채우고 가치의 합이 최대로 짐을 골라서 채우세요.
만약 물건을 쪼갤 수 있다면 탐욕(Greedy) 알고리즘으로 쉽게 해결할 수 있어요. 
하지만 쪼갤 수 없다면 모든 경우의 수를 따져봐야 하기 때문에 동적 프로그래밍(Dynamic Programming) 방법으로 해결해야 합니다. 모든 경우의 수를 따지는 것은 자료의 개수가 커지면 최적해를 구하는데 너무 오래 걸릴 수 있어요.
배낭 채우기 문제에서 물건 목록을 정하면 A 무게 이상인지 가치의 합이 얼마인지를 구하는 것은 쉬운 문제죠.
이처럼 문제의 답을 제시하면 판별하기는 쉽지만 문제 해결 방법을 찾는 것이 어려운 문제를 NP 문제라고 말해요.

NP 문제는 인공 지능 연구에 좋은 소재입니다.

NP 완전(NP Completeness)에서 완전(Completeness)는 most extreme이라는 의미로 쓰인 것입니다.

따라서 NP 부류에서도 극단적으로 어려운 문제라고 볼 수 있는 것이죠.

앞으로 IT 이야기를 진행하면서 NP문제와 여NP 문제에 관해 다시 언급할 때가 있을 거예요.

너무 간략하게 정리한 것이라 말하는 이들도 계시겠지만 진입 장벽을 낮추기 위함이니 너그러이 이해해 주시길...

알고리즘 이야기

인간의 뇌와 슈퍼 컴퓨터

지능형 에이전트(Intelligent agent)

[출처] P - NP 문제|작성자 언제나 휴일