NP Complete Problems

Class P: Polynomial time (다항시간) 안에 작동되는 알고리즘.

Class NP: 다항시간 안에 문제를 풀 수 있는지 없는지 검증 가능한 것.

NP Hard:  every problem in NP is reducible to Q (NP에 있는 어떤 문제보다도 Q가 어려울 때, Q를 NP hard라고 함.)

NP complete: NP에 속해있으면서, NP 속 모든 문제보다 어려운 문제.

Polynomial Reductions: 문제 X와 Y가 있을 때, X를 풀 수 있으면 Y도 풀 수 있다. 이것은 곧 X가 Y보다 쉽지는 않다는 것을 뜻한다. Y를 다항시간 안에 X instance 형태로 바꿀 수 있다면, Y를 풀 수 있다. >>Y is polynomial reducible to X.

 

1. SET-COVER: m집합 안에서 k개 이내로 뽑은 후 합집합할 때, m집합과 같아지는가? NP COMPLETE

2. SUBSET-SUM: 집합 K의 부분집합 중 그 집합의 원소를 다 더한 값이 0이 될 수 있나? NP COMPLETE

3. 0/1 Knapsack: 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합이 있나?

4. Hamiltonian-Cycle: 어떤 그래프에서 모든 꼭지점을 단 한번만 지나가는 경로가 있나?