Decision Problem
yes 나 no 로 대답할 수 있는 문제이다.
P (Polynomial Time)
Decision problem를 푸는데 걸리는 시간이 polynomial time이 걸리는 문제의 집합이다. polynomial time 시간 내에 yes 나 no 라는 답이 도출되는 알고리즘이 존재하는 문제들의 집합이다.
NP (Non-deterministic Polynomial Time)
Decision problem을 증명하기 위해 걸리는 시간이 polynomial time이 걸리는 문제의 집합이다. 푸는 것이 아닌 증명하는 것이라는 것에 주의하라. 3*10은 30이라는 것이 참이라는 것을 polynomial time에 증명할 수 있으며 답을 구하는데 걸리는 시간이 polynomial time 안에 가능한 P가 존재한다.
Behnam Esfahbod [CC BY-SA 3.0], via Wikimedia Commons
NP-Hard
NP의 모든 문제가 polynomial time 안에 다른 문제 H로 치환될 수 있다면 H는 NP-hardness 이다.(NP의 가장 어려운 문제만큼 어려운 문제의 집합이라는 의미도 된다고 한다.) 예를 들자면 b = f(a)가 있는데(b는 참, 거짓으로만 나온다.) 값a가 polynomial time 안에 c로 변환이 되며 g(c), 즉 d의 값이 f(a), 즉 b의 값과 동일하다면 우리는 함수g를 풀어도 함수f와 동일한 값을 얻을 수 있으므로 더 쉬운 것을 풀면 된다. 즉 함수g를 polynomial time 안에 푼다면 모든 NP 문제가 polynomial time 안에 풀릴 수 있다는 말이다.
NP-Complete
NP집합에 속하며 NP hard에 속하는 문제이다.
NP-Complete 문제를 polynomial time 안에 푸는 것이 가능한지 증명하는 것에 대해 많은 상금이 걸려있다. 이 것이 증명된다면 NP 문제들이 polynomial time 내에 NP hard 문제로 치환되어서 polynomial time 안에 풀리는 것이 가능해 진다.
'알고리즘' 카테고리의 다른 글
알고리즘의 시간 복잡도에 대해 알아보기 (0) | 2016.06.07 |
---|---|
이분법, 삼분검색, 모듈라 연산 알고리즘에 대해 알아보기 (0) | 2016.06.04 |
탐욕법, 조합탐색 알고리즘에 대해 알아보기 (0) | 2016.06.04 |
여러 가지 알고리즘에 대해 간단히 알아보기 (0) | 2016.06.02 |
비교를 사용하지 않는 정렬방식 알아보기 (0) | 2016.02.06 |
요소끼리의 비교를 통한 정렬방법들 알아보기 (0) | 2016.02.05 |