매번 알았다가 까먹는 P, NP 개념들 정리 차원
- P (deterministic Polynomial)
- 적당한 시간 안에 계산해 낼 수 있는 문제 또는 알고리즘.
- 예: 변수와 관련된 지수가 constant(예: 1 또는 2 등)로 정해진 경우 처럼, 알고리즘의 속도가 다항식으로 표현되는 문제들
- 알고리즘의 복잡도가 O(n^x)로 표현됨
- 즉, 컴퓨터가 적당한 시간(다항시간, polynomial time) 이내에 해결할 수 있는 (쉬운) 문제들
- NP (Non-deterministic Polynomial) [비결정 다항식]
- 알고리즘의 속도가 다항식으로 표현될 수 있는 지 여부가 알려지지 않은 문제들
- 예: 문제의 변수와 관련된 지수 역시 상수가 아니라 변수로 표현되는 경우
- 다만, 해결 방법은 모르더라도, 다항 시간(polynomial time)에 답의 존재 유무를 확인할 수 있음
- 따라서, P에 해당하는 문제는 NP에도 속한다. 즉, P는 문제 해결이 다항식 시간 내에 이루어지므로 ,답의 존재 유무 판별 또한 다항식 시간 내에 확인 가능하기 때문이다.
- NP-hard
- 모든 경우의 수를 전부 확인해 보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제
- at least as hard as the hardest problems in NP
- 예: 세일즈맨의 여행 문제(Salesman Traveling)
- NP에 속하는 모든 문제가 다항 시간내에 다대일 축소변환(many-one reducible)될 수 있는 문제 H.
- NP-Complete
- 어떤 문제가 NP에 속하면서, 동시에 NP-hard에 속하는 경우
- 즉, 다향식으로 표현될 수 있는 지도 알려지지 않았으면서, 동시에, 무식하게 다 구해보지 않고 풀 수 있는 방법이 알려져 있지 않을 때.
- 물론, 다항시간 내에 해결 가능한지는 알 수 없지만, 문제를 해결하는 데 있어 (다항시간 축소 변환에만해도 다항 시간이 소요되기 때문에) 적어도 다항시간 이상은 걸릴 수 밖에 없음
- approximation/ 근사 알고리즘
- heuristic
- greedy
P = NP ?
- NP에 속하는 문제들을 다항식(P)를 이용해서 해결할 수 있는가?
- Exponential time에 해결 가능한 모든 NP 문제를 P로 해결 할 수 있는가?
