Np Complete, Polynominal Algorithm

문제해결기법 시간에 교수님이 NP Problem에 대해서 간략히 소개해 주셨다.

그런데 시간이 너무 부족해서 교수님이 빠르게 빠르게 설명하셔서 미처 내용을 다 이해하지 못 했고, 집에와서 다시 구글링해 보았다.

NP Problem

• NP문제를 쉽게 설명하자면 yes/no로 답할 수 있는 문제중에, yes라는 답에 해당하는 구체적인 예를 줬을때, 그것이 yes가 맞다는것을 다항(polynomial)시간안에 알 수 있으면 NP문제이다.

P Problem

• P문제는 NP문제 중에서도 답(ex 방문경로) 조차도 빠른 시간안에 알 수 있는 문제. P문제도 NP문제에 속한다.

NP-Complete Problem

• 모든 NP 문제들이 빠른 시간안에 변환(reduction)이 될 수 있는 문제. 빠른 시간안에 NP-Complete문제로 변환될 수 있기 때문에, NP-Complete문제만 풀면 모든 NP문제를 빠르게 풀 수 있다.

NP-HARD

• 정말 어려운 문제로, NP문제가 아닌 문제
• ex) TSP(Travelling-Salesman-Problem, 외판원 방문 문제): 총 길이가 k이하인 길이 있느냐가 아니라, 가장 최적인 길이 뭐냐라는 문제같은거다.

P = NP ?

• 이게 증명된다면 NP문제에 해당하는 모든 문제를 빠른시간에 푸는게 가능하다.
• 아직까지 증명되지 않음