출처: 1
P 분류(P class)
P 분류는 판정 문제들을 분류하는 방법중 하나이다. 여기서 판정 문제란 입력값에 대해 예/아니오 답을 내릴 수 있는 문제를 말한다. P 분류는 결정론적 튜링 기계에서 다항식 시간 안에 풀 수 있는 모든 문제를 포함한다.
NOTE튜링 기계: 무언가를 계산하는 기계를 대표하는 가상의 장치
- 일반적인 컴퓨터 알고리즘을 수행할 수 있음결정론적 튜링 기계
결정론적 튜링기계란?
- 어떤 명령어 실행 뒤, 다음 실행할 명령어가 확정됨
- 코어 하나에서 명령어를 순서대로 실행한다 생각할 것
- 즉, 코어 하나에서 실행되는 다항식 시간 알고리즘이 있는 문제는 P
NP 분류(NP class)
NP(비결정적 다항식 시간)는 많은 사람들이 오해하는 것처럼 ‘Not P’가 아니다. 이는 비결정론적 튜링 기계에서 다항식 시간 안에 해결할 수 있는 문제들을 의미한다.
NOTE비결정론 튜링 기계의 특징
- 비결정론적 튜링 기계어떤 명령어 실행 뒤, 다음 실행할 명령어가 확정되지 않음
- 여러 개의 다음 명령어를 병렬적으로 실행하는 기계라고 생각하면 됨
- 사실상 현실에서 볼 수 없는 가상의 장치라고 생각하면 됨
(결정론적) 튜링 기계에서의 NP 문제
결정론적 튜링 기계에서 NP 문제는 일단 답이 있으면 그 답이 맞는지를 다항식 시간 안에 검증할 수 있다. 문제를 푸는 데는 지수시간이 걸릴수도 있지만, 그래도 다항식 시간안에 검증이 가능하다.
랜덤 접근 기계는 결정론적 튜링 기계
보통 알고리즘 공부할 때 사용하는 기계가 랜덤 접근 기계이다. 랜덤 접근 기계는 레지스터를 갖춘 CPU 1개를 말한다. 이 랜덤 접근 기계로 NP 문제를 일반적인 방법으로 풀기에는 조금 느릴 수도 있다. 그래서 대신 무작위, 근사, 휴리스틱 알고리즘 등을 이용하여 문제를 푼다.
다음 프로그램은 P? NP?
public static boolean hasGreater(int[] nums, int k) {
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > k) {
return true;
}
}
return false;
}
이 문제는 P이자 NP이다. 이 문제는 다항식 시간안에 풀 수 있다.() 하지만 병렬적으로도 다항식 시간 안에 풀 수 있는 문제이다.
한 코어에서 다항식 시간 안에 풀 수 있다면 병렬적으로도 풀 수 있다.
P 또는 NP가 아님!
위 결정론적, 비결정론적 예시를 보면 더 이해가 될 수 있겠지만, P와 NP는 반대되는 개념이 아니다. 둘 사이의 판단 기준이 아예 다르기 때문에 NP가 Not P가 아니다. 사실 모든 P 문제는 NP 문제이다.
NP - 완전(NP-complete, NPC) 문제
NP-완전 문제는 NP 문제중 일부이다. 모든 NP 문제는 NP-완전 문제로 환원이 가능하다.(다항식 시간 안에) 그리고 여전히 NP 문제이기 때문에 다항식 시간 안에 답 검증이 가능하다. 이 NP-완전 문제는 다른 NP문제들중에서도 일반적인 알고리즘(모든 문제를 설명 가능한 문제)이기 때문에 NP 중에서도 가장 어려운 문제라고 할 수 있다.
대표적인 NP-완전 문제들
외판원 문제(판정 버전)
- 주어진 길이 L을 넘지 않는 경로가 존재하는지 판정
- 모든 도시를 한 번씩 방문하는 최단 경로 찾기
배낭 문제
- 크기와 가치가 다른 물건들을 제한된 크기의 배낭에 넣기
- 특정 가치 V 이상을 달성할 수 있는지 판정
- 의사 다항식 시간에 해결 가능한 약한 NP-완전 문제의 예시
- 동적 계획법이나 그리디 알고리즘으로 해결 가능
NP - 난해(NP - hard) 문제(참고)
P vs NP 문제
P NP 문제는 P 또는 NP냐를 논하는 문제가 아니다. P와 NP가 같은지 아닌지를 논하는 문제이다.
앞서 언급했듯이, NP- 완전 문제는 NP 문제 문제중에서 가장 어려운 문제이다. 그런데 만약 NP - 완전 문제 중 하나라도 다항식 시간 안에 풀 수 있게 되면 어떻게 될까? 이 문제는 P가 된다. 그렇게 되면 모든 NP 문제를 NP-완전 문제로 다항식 시간 안에 환원할 수 있게 된다. 따라서 모든 NP 문제가 P가 된다.(아직 다항식 시간안에 검증이 되는 알고리즘을 발견하지 못했기 때문에 P가 아니다.)
P = NP가 증명된다면?
만약 P = NP가 증명된다면 현대 사회에 미치는 영향은 매우 클 것이다. 현재 해결이 어려운 많은 최적화 문제들을 효율적으로 해결 가능하다. 동시에 현대 암호체계의 근본적인 재검토가 필요하다. 또한, 인공지능과 기계학습 분야가 혁신적으로 발전 가능하게 된다.
P vs NP 문제 증명법
를 증명하는 방법은 무엇일까? 간단하다. NP- 완전 문제 중에 하나라도 다항식 시간 안에 풀면 된다. 이 알고리즘을 발견하는 순간 이 논란은 종식된다. (하지만 지금까지 단 한개도 발견하지 못했다.) 반대로 를 증명하는 방법은 있을까? 없다. 를 증명 못하는 시간이 길어질수록 개연성만 높아진다. 현재 그래서 모두 라고 추측하고 있다.
Footnotes
이 블로그 포스팅은 자료구조와 알고리즘(김포프, 유데미)를 기반으로 만들어졌음을 밝힙니다. ↩