ezwy

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 안에 풀리는 것이 가능해 진다.