제 13강 근사 알고리즘(NP - 완전 문제와 NP-하드 문제, NP - 완전 문제의 종류 )

학습 목표

1. 튜링기계, 다항 시간 알고리즘, 판정 문제의 개념을 이해할 수 있다.

2. 클래스 P와 클래스 NP의 개념을 이해할 수 있따.

3. NP-완전 문제와 NP-하드 문제의 개념과 종류를 이해할 수 있다.

4. NP- 하드 문제의 다양한 근사 알고리즘을 이해할 수 있따.

 

주요 용어

결정론적 튜링기계, 비결정론적 튜링 기계, 쉬운 문제, 어려운 문제, 다항 시간 알고리즘, 판정 문제, 클래스 P, 변환, NP-완전문제(외판원문제, 0/1 배낭 문제, CNF 만족성 문제, 해밀토니언 사이클 문제, 퀘 채우기 문제, 파티션 문제, 클리크 판정 문제, 버텍스 커버문제), NP-하드 문제, NP-완전성, 근사 알고리즘

 

7.3 NP - 완전 문제와 NP-하드 문제

 

7.3.1 변환 

> 문제 A 가 문제 B로 변환 reduction 된다.

  - 문제 A 의 입력과 출력을 문제 B의 입력과 출력 형태로 바꿀 수 있고,

여기에 문제 B를 해결하는 알고리즘을 적용함으로써 궁극적으로 문제 A를 풀 수 있다.

  :  다항식 시간 변환 -> " 입력과 출력의 형태를 바꾸는 데 다항 시간이 소요"

ex)

 문제 A  >>>>   알고리즘 A >>>> 출력 A

    ↓                                            ↑

 문제 B  >>>>   알고리즘 B >>>>  출력 B

 

 

7.3.2 NP - 완전 문제

> 완전 complete 문제

  - 어떤 부류에 속하는 모든 문제가 그 부류에 속하는 어떤 문제 R로 다항식 시간 변환이 가능하다면 문제 R을 그 부류의 완전 문제라고 함

  - 해당 부류의 모든 문제를 대표하는 문제

   : 완전 문제 R을 다항 시간에 해결 할 수 있다면 그 부류의 다른 모든 문제도 결국 다항 시간에 해결가능

  - 해당 부류에서 가장 어려운 문제

 

> NP- 완전문제

 - 클래스 NP 에 속하는 모든 문제가 주어진 어떤 문제 A로 다항식 시간 변환되고,

   문제 A가 클래스 NP에서 속하는 경우, 문제 A 를 NP-완전 문제라고 함

 

> 하드 문제

 - 어떤 부류에 속하는 모든 문제가 어떤 문제 R로 다항식 시간 변환이 가능하면 문제 R을 그 부류의 하드 문제라고 함

  -> 문제 R이 해당 부류에 속한다는 조건이 없는 경우

 - 해당 부류에 속하는 어떤 문제보다 풀기 어렵거나 비슷한 정도로 풀기 힘든 문제

 

> NP - 하드 문제

  - 클래스 NP에 속하는 모든 문제가 주어진 어떤 문제 A로 다항식 시간에 변환되는 경우, 문제 A를 NP-하드문제라고 함

     문제 A가 클래스 NP에서 속하지 않는 경우, 문제 A 를 NP- 하드 문제라고 함

 

> NP - 완전 문제와 NP - 하드 문제의 관계 

  - 모든 NP- 완전 문제는 NP- 하드 문제이다.

  - 하지만, 모든 NP-하드 문제가 NP- 완전 문제는 아니다.

 

 

---

- NP - 완전 문제의 종류 -

 

(1) 외판원 문제 ( TSP: traveling salesman problem )

- 여러 도시와 도시간의 이동에 필요한 비용이 주어진 경우 비용 R 이하로 모든 도시를 한번씩만 방문하고 처음 도시로 돌아오는 방법이 존재하는지 판정하는 문제 

 

 

(2) 0/1 배낭 문제

 - 특정 용량을 갖는 배낭과 n 개의 물체가 주어지고 각 물체마다 무게와 이익이 주어질 때, 배낭에 담긴 물체의 이익의 합이 R 이상이 되도록 배낭에 물체를 담는 방법이 존재하는지 판정하는 문제

 : 배낭의 용량을 초과할 수 없고, 물체를 쪼갤 수 없다.

 

(3) CNF 만족성 문제

 - 정규곱형 ( Conjuctuve Normal Form)으로 주어진 논리식의 리터럴들에 참 또는 거짓 값을 적절히 지정하여 전체 논리식의 값을 참으로 만들 수 있는 지를 판정하는 문제

 

 

(4) 해밀토니언 사이클 문제
 - 무방향 그래프 G가 주어졌을 때, G의 모든 정점을 한 번씩만 지나가는 사이클이 존재하는지 판정하는 문제

 

 

 

 

 

(5) 퀘 채우기 문제

 - 용량이 1인 무한개의 퀘와 다양한 크기의 개체가 n 개 주어진 경우. R개의 퀘로 n개의 개체를 전부 수용할 수 있는지 판정하는 문제

 

 

 

(6) 파티션 문제

  - n개의 양의 정수가 주어졌을 때, 각 집합에 포함된 수의 합이 동일하도록 n개의 양의 정수를 두 개의 집합으로 나눌 수 있는지 판정하는 문제

 

(7) 클리크 (clique) 판정 문제

 - 그래프 G 와 정수 K가 주어졌을 때, G가 크기 K 인 클리크를 갖는지 여부를 판정하는 문제

   : k개의 정점으로 완전 그래프(모든 정점 사이에 간선이 존재)가 되는 G의 부분 그래프

 

(8) 버켁스 커버 문제

 - 그래프 G와 정수 K가 주어졌을 때, G가 크기 k인 버텍스 커버를 갖는지 여부를 판정하는 문제

  : 버텍스 커버 >> 모든 간선이 최소한 하나 이상의 정점에 부수하는 정점의 부분 집합

  : 버텍스 커버의 크기 >> 버텍스 커버를 구성하는 정점의 개수

 

 

 

NP-완전성의 증명

(1) 알려진 하나의 NP-완전 문제가 해당 문제로 다항식 시간 변환됨을 보인다.

(2) 해당 문제를 푸는 비결정론적 튜링 기계가 존재함을 보인다.