NP-Completeness

Yes 대답이 나오는 해를 제공하면 이를 다항식 시간에 확인 할 수 있으면 됨

• Yes/NO 문제

  해밀토니안 경로가 있는가

• 최적화 문제

  가장 짧은 해밀토니안 경로의 길이는 얼마인가

NP 문제 변환

부분 집합의 합

• 다항식 시간의 문제로 변환

분할 문제

여행자 문제 (TSP)

• 각 도시를 한번씩 방문하고 돌아오는 최단 경로

  → 거리가 K보다 짧은 경로가 있는가 의 결정 문제로 변형

NP-Hard

모든 NP 문제가 L로 다항식 시간에 변환가능하다

• L이 NP이면서 NP-Hard이면 NP-Complete이다.