NP-Complete Problems

Optimization Problem vs Decision Problem

- Optimization Problem

- Find a feasible solution with the best value

- SHORTEST-PATH  가장 적은 edge로 가는 경로 찾기

- Decision Problem

- 답이 yes or no

- PATH: given a graph G and vertices u and v, and an integer k, is there a path from u to consisting of at most k edges?  k 이하로 가는 경로가 존재하는가?

 

Polynomial Time: Class P

- 어떤 상수 k에 대해 T(n)=O(nk) 라면 그 알고리즘은 Polynomial time(다항식 시간)에 수행된다.

- 어떤 문제에 대해 polynomial-time algorithm이 존재한다면 그 problem은 class P에 있다.

- 알고리즘이 polynomial time에 수행된다면 “efficient”

 

Some Problems are Very Hard

- 어떤 문제는, 알려진 polynomial time algorithm이 존재하지 않음.

- 0/1 knapsack problem, traveling salesperson problem(complete weighted graph가 주어지고, 최소비용으로 모든 vertex를 한번에 방문하는)

- Undecidable problems: 정확한 예 또는 아니오로 이끄는 알고리즘을 구성하는 것이 불가능한 결정 문제

 

- 0/1 knapsack problem

- input: n개의 item. i번째 item: (Vi dollar, Wi weight), W의 무게만큼 담을 수 있는 가방

- output: W이하 무게로 가장 많은 이익을 갖는 item들 선택 -> W이하 무게로 k 이상의 이익을 갖는 item들이 존재하는가 (optimal 에서 decision으로 바꿈)

- 제한 조건

1. 각 item을 가져가든지/놓고가든지

2. item의 일부분만 가져갈 수 x

3. 한 item은 한 번만 가져갈 수 있음

 

Non-Deterministic Polynomial Time: Class NP (비결정 다항 시간)

- 어떤 문제에 대해 non-deterministic polynomial-time algorithm이 존재하면 그 문제는 class NP에 있다.

­- 즉, 그 solution(certificate)을 다항 시간에 vertify 가능하다.

- 다항시간 안에 certificate를 verify만 할 수 있으면 NP

- 클래스 P에 속하는 문제들은 모두 클래스 NP에 속한다.

- P⊂NP인건 아는데, P=NP인가? (아무도 증명 못했음.)

- (비결정론적 알고리즘(Nondeterministic algorithm)은 결정론적 알고리즘과는 달리, 동일한 입력이 주어지더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 의미한다.)

 

NP Example

- 문제: 어떤 그래프가 weight가 최대 K인 MST(minimum spanning tree)를 갖는지 결정 (yes/no)

- Verification Algorithm: yes면 yes라 하고, 아니면 대답 안 함

- Analysis: certifictate를 Test하는 데 O(n+m) 시간이 걸리므로 그 알고리즘은 polynomial time에 수행 가능.

 

중간 정리

- class P: the class of decision problems that are polynomial bounded.

- class NP: the class of decision problems for which there is a polynomially bounded non-deterministic algorithm.

 

The Class NP-Complete

- problem Q가 NP-hard이다: 클래스 NP 안에 있는 어떤 문제보다 쉽지 않다 (Q가 NP안에 포함된다고 보장x)

- problem Q가 NP-complete이다: NP-hard면서 NP에 있는 문제

- 문제 P가 문제 Q로 reducible:

- 다음과 같은 polynomial reduction fuction (다항 축소변환 함수) T가 존재한다:

- 모든 string x(P의 input)에 대해,

- x가 P의 yes input이라면, T(x)는 Q에 대해 yes input이다.

- x가 P의 no input이라면, T(x)는 Q에 대해 no input이다.

- T는 다항 bounded time에 계산 가능하다.

- ex) P: N개 정수 중 최솟값 찾기, Q: 정렬하기

- 변환: 다항시간, Q: 다항시간이면 P: 다항시간에 해결 가능

 

Some NP-Complete Problems

- SET-COVER: 적은 수의 union으로 universe 만들기(최소 집합수)

- |U|={1,2,3,4,5}, S={{1,2,3},{2,4},{3,4},{4,5}}일 때 -> {1,2,3},{4,5} 고르면 최소

- SUBSET-SUM: n개 원소를 갖는 집합 S와 positive int k가 주어졌을 때, 원소들의 합이 정확히 t인 subset이 존재하는가?

- 위 둘다 reduction from VERTEX-COVER에 의해 NP-complete이다.

 

Traveling Salesperson Problem

- NP-complete by reduction from Hamiltonian-Cycle

- Hamiltonian cycle 문제를 TSP를 이용해 풀 수 있음

 

**증명해보자.

- P: Hamiltonian-cycle problem

- Q: TSP (NPC라고 증명하고 싶은 문제)

(그래프  G의 해밀턴 경로 p는 G의 모든 꼭짓점을 포함하는 경로이다. (정의에 따라, 경로는 꼭짓점을 중복하여 거치지 않는 보행이다.) 해밀턴 순환(Hamiltonian cycle)은 해밀턴 경로인 순환이다.)

 

1. class NP임을 증명

- certificate가 제시됐을 때, edge들의 sum이 k 이내인지 확인 -> 다항시간에 verify 가능 -> NP임

2. NP-hard임을 증명

1) 다항시간에 input을 변환 (k=0)

- H.C에 있는, 기존 edge의 weight은 0, 새로 채운 edge의 weight은 1로 두고 k=0 되게 하면 기존 edge들만 방문하는 경로가 됨.

2) 문제의 답이 일치함을 보임

- 0으로만 방문하는 cycle이 존재 -> H.C에서도 존재

- 0으로만 방문하는 cycle이 존재x(weight 1인 edge를 하나라도 지나감) -> H.C에서도 존재x

결론: NP이고 NP-Hard이므로 NP-Complete이다.

 

SAT (Satisfiability)

: CNF (논리곱 정규형)

- booleann formula S에 대해, S를 1로 만드는 input 조합이 존재하는가?

1. CNF-SAT이 NP임을 보인다. -> 수식 계산은 다항 시간에 verify 가능함. NP임.

2. NP-Hard임을 보인다 -> circuit-sat으로부터 증명 가능 -> NPC이다.