P, NP, NP-Hard

문제가 주어졌을 때, 이 문제가 현실적으로 풀 수 있는가 를 정의할때 쓰이는 개념들이다.

P는 Polynomial, 한글로는 다항식을 의미한다.

P군에 속하는 문제들은 다항식 시간에 해결할 수 있는 문제들을 의미한다.

NP는 Non deterministic Polynomial을 뜻한다.

NP군에 속하는 문제들은 다항식 시간에 확인 가능한 문제들을 의미한다.

이게 무슨 뜻이냐면, 문제의 답과 그에 대한 근거가 주어졌을때, 그것이 옳은 근거임을 다항식 시간에 확인 가능하다는 뜻이다.

* P와 NP의 포함관계

P는 NP에 포함될 것이라고 강력하게 추정되고 있을 뿐이다. 그렇지만 NP에 P가 아닌 문제도 포함되는지는 아직 아무도 증명하지 못했다. 이는 클레이 연구소에서 21세기를 맞아 정한 7개의 백만불짜리 문제 중 하나이다. 

NP-hard는 

모든 NP 문제가 주어진 문제 A에 대하여 다항식 시간 변환이 가능하면 A는 NP-hard이다.

하지만 모든 NP 문제를 다 나열하긴 불가능하니 그냥

어떤 하나의 NP 문제가 주어진 문제 A에 대하여 다항식 시간 변환이 가능하면 A는 NP-hard이다. 라고 정의하면 된다,

NP-Complete는 NP-hard보다 조금 더 좁은 개념으로 다음 두 조건을 만족하면 된다.

1. A는 NP이다.

2. A는 NP-hard이다.