P-NP 문제(P-NP problems)

 

 

P: deterministic Polynomial time

NP: Non-deterministic Polynomial time

 

Polynomial time이란 수식으로 표현할 수 있는, 즉 유한한 시간이라는 의미이다.

 

P: 풀기 쉽고 답이 맞는지 확인하기 쉬운 문제들이다.

 

NP: 풀기는 어렵지만 답이 있다면 답이 맞는지 검증하기는 쉬운 문제들이다. 예) 스도쿠

 

NP-hard: 변환(transform), 축소(reducing) 기법들을 이용해서 NP 문제를 또 다른 형태로 변경시킨 것이다. 아직 NP인지 P인지 조차 알 수 없는 경우에 해당한다. 이런 이유로 다이어그램에서 점선으로 표시하였다.

 

NP-Complete: 변환 또는 축소 기법으로 NP문제를 다른 형태로 변경시킨 경우이다. 다만 이 경우에는 변경된 문제가 NP인지는 확실하게(complete) 알고 있다.

 

결국 우리가 도전할 수 있는 문제들을 아래와 같이 정리해 볼 수 있다.

① NP 문제를 (P로 변환한 후) 풀기

② NP-hard 문제가 NP-Complete 문제인지 검증하기

 

■