1. NP완전문제

• p 문제: 다항식 시간알고리즘을 가진 문제의 집합
  ex) O(n), O(n^2), O(nlogn), O(n^3)

• NP 문제(비결정적 다항식 문제): 다항식 시간의 알고리즘이 아직 발견되지 않은 문제

• NP 하드문제: NP만큼 어려운 문제

1.1. P문제

다항식 시간알고리즘을 가진 문제의 집합
ex) O(n), O(n^2), O(nlogn), O(n^3)
시간적 복잡도가 O(n^k)으로 현실적으로 해결이 가능한 문제들의 집합

1.2. NP 완전문제

지수시간의 시간복잡도를 가진 알고리즘으로 해결되는 문제들의 집합

• 특성
  비결정적 다항식
  NP완전문제중 단 한문제라도 다항식 시간(P문제)안에 해를 구할 수 있다면 다른 모든 NP완전문제가 P문제가 된다.
  
  위사진의 집합관계는 증명되지는 않았다.
  P와 NP사이의 관계를 모름

1.3. NP 문제(결정 문제)

비결정적 다항식 시간을 가진 알고리즘
NP문제에 대해서 해를 다항식 시간 안에 확인하는 알고리즘
(해를 찾는 알고리즘 X)

1. 주어진 입력에 대해서 하나의 해를 추측함
2. 추측한 해를 다항식 시간안에 그 해가 맞는지 틀린지 확인하는 알고리즘

1.4. NP-완전 문제의 특성

NP-완전문제를 다른 문제로 변환 또는 환원해야함

1. A문제를 B문제로 변환한다
2. B문제를 해결하는 알고리즘으로 B의 문제를 해결한다.
3. 해결된 B의 해를 A문제의 해로 변환한다
   

1.4.1. 부분문제의 합 문제

정수 집합 S에 대해 원소의 합이 K가 되는 부분 집합을 찾는 문제

ex)
S = {20, 35, 45, 70, 80}
K = 105일 경우
해 = {35, 70}

NP완전문제