NP문제

yes 대답이 나오는 해를 제공했을 때, yes 대답을 내는 해라는 사실을 polynomial time 내에 확인가능하다면 NP 문제라고 한다.


* 다항식 시간내에 구할수 있을지 없을지 non-deterministic하다. 풀 수 도 있고 못 풀 수도 있다는 말이다.


Nondeterministic algorithm
 1. 추측 단계 : 문제의 사례가 주어지면 임의의 문자열 S를 만든다.
 2. 검증 단계 : 문제와 문자열 S를 입력 받고, 확인한 뒤 true, false로 return 한다.
 3. 출력 단계 : true이면 알고리즘은 yes, 아니면 출력이 없다고 한다.

NP-hard : 어떤 문제 P가 Q에 polynomial 시간 내에 reduction 된다면 Q는 NP-hard라고 한다.

NP-complete : NP-Hard이고 NP에도 속한다면 NP-complete라 한다.

아래 그림을 통해 어떤 관계인지 한눈에 알 수 있다.

< P와 NP의 포함 관계>

<NP와 NP-Complte, NP-Hard의 관계>

* 거대한 자연수의 약수를 찾는 문제
 소수의 곱으로 이루어진 거대한 자연수는 분명히 소인수분해를 할 수는 있지만 그 소수를 모른다면 소인수분해를 할 수 없다. 이것은 소수를 알고있다면 다항식 시간내에 풀 수 있는 P문제이지만 약수를 찾을 수 없는 경우가 있기 때문에 NP문제이다.



왜 NP 이론을 공부하는가??

• 어떤 문제가 NP-Complete/Hard인것이 확인되면
• 쉬운 알고리즘을 찾으려는 헛된 노력은 일단 중지한다
• 주어진 시간 예산 내에서 최대한 좋은 해를 찾는 알고리즘(heuristic) 개발에 집중한다.

참고 

- http://kylog.tistory.com/46 (굉장히 쉽게 P, NP 관계를 설명해놨다)

- 쉽게 배우는 알고리즘