P,NP,NP-Hard,NP-Complete에 대한 간략한 정리

P 
  : Deterministic Polynomial Time 의 약자이다.
  : Polynomial time 이내에 해결, 곧 답을 찾을 수 있는 문제들을 의미한다.
  : 즉 알고리즘의 복잡도가 O(n^x)로 표현되는 모든 문제들을 말한다.

NP
  : Non Deterministic Polynomial Time의 약자이다.
  : Polynomial time에 답의 존재 유무를 확인할 수 있는 문제를 말한다.
  : 답을 줬을 때 그 답이 맞는지를 Polynomial한 시간 이내에 찾을 수 있는 문제들을 의미한다.
  : 답이 Polynomial Time 안에 해결 가능한지, 불가능한지는 모르지만 답의 유무는 확인
    가능한 문제들의 집합이다.

NP-Hard
  : at least hard as the hardest problem in NP
  : 답을 줘도 답이 맞는지 P-time이내에 확인할 길이 없고, 답을 구할 수도 없는 문제를 의미한다.


NP-Complete 
  : 모든 NP문제들을 P-Time 이내에 Reduction(변환)할 수 있는 문제를 NP-Complete라고한다.
  : 결국 NP-Complete문제를 해결한다면 모든 NP문제를 풀 수 있다는 결론이 나온다.
  : NP-Complete 문제를 해결한다면 P=NP라는 가설이 해결된다는 의미이지 않을까 싶다.