[알고리즘 12강] NP 완전문제

1. 기본 개념

a. 튜링 머신

• 컴퓨터의 이론적 모델

  • 무한한 길이의 테이프, 유한한 개수의 기호와 상태
    상태와 기호에 따른 헤드의 동작을 정해둔 규칙

  • 현재 상태와 읽은 기호에 따라 헤드가 테이프에 기호를 쓰거나 좌우로 이동

b. 다항 시간 알고리즘

알고리즘의 수행 시간이 입력 크기 n에 대한 다항식으로 표현되는 알고리즘

• $O(n), O(1), O(n^2).....$
• $O(2^n)$ -> 지수 시간 알고리즘

c. 문제의 난이도

• 쉬운 문제

  • 결정론적 튜링 머신을 이용한 다항 시간 알고리즘이 존재

• 어려운 문제

  • 결정론적 튜링 머신을 이용한 다항 시간 알고리즘의 존재여부를 알 수 없는 문제

d. 문제의 종류

• 판정 문제

  • 문제의 해가 "예" 또는 "아니오"로 나오는 문제

    ex) $n * n이 n + n보다 작은 자연수 n이 존재 하는가?$

• 최적화 문제

  • 최소값이나 최대값을 구하는 문제

    ex) $n * n이 n+n보다 작은 자연수 n 중 가장 큰 수를 찾으시오$

가) 0/1 배낭 문제 예시

• 최적화 문제

  $\displaystyle\sum_{i=1}^{n}{W_iX_i} \leq C$ 이면서 $\displaystyle\sum_{i=1}^{n}{p_ix_i}$를 최대로 하는 $x_i$를 구하라

• 판정 문제

  $\displaystyle\sum_{i=1}^{n}{W_iX_i} \leq C$ 이면서 $\displaystyle\sum_{i=1}^{n}{p_ix_i} \geq R$인
  $x_i, 1\leq i \leq n$들의 값이 존재 하는가?

---

2. NP-완전 문제의 개념

클래스 NP에 속하는 모든 판정 문제가, 주어진 어떤 문제로 다항식 시간에
변환되고 그 문제가 클래스 NP에 속하는 경우, 그 주어진 문제를 NP-완전 문제라 한다.

• 다항식 시간 알고리즘이 아직 만들어지지 않았고,
  그렇다고해서 그러한 알고리즘이 존재하지 않는다고 증명되지도 않은 문제

a. CNF 만족성 문제 [NP-완전 문제의 예시]

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

b. 해밀토니언 사이클 문제 [NP-완전 문제의 예시]

무방향 그래프 G가 해밀토니언 사이틀을 갖는지 판정하는 문제

• 해밀토니언 사이클
  • 그래프 G의 한 정점 A에서 출발하여 모든 정점을 정확히 한 번 통과한 후
    A로 다시 돌아오는 경로

c. 외판원 문제 [NP-완전 문제의 예시]

각 간선에 정수의 가중치가 부여된 무방향 완전 그래프 G가 주어졌을 때,
G가 최소의 전체 가중치를 갖는 해밀토니언 사이클의 존재 여부를 판정하는 문제

---

3. 비결정론적 알고리즘

a. 결정론적 튜링 머신

테이프의 위치를 바꾸거나 쓰인 기호를 바꿀 때,
한 가지 상태로만 변경이 발생

b. 비결정론적 튜링 머신

하나 이상의 상태로 바뀔 수 있거나
혹은 바뀔 상태가 없을 수 있음

• 연산 결과가 상황에 따라 달라질 수 있는 연산을 수행

c. 결정론적 알고리즘

결과가 유일하게 정의된 연산만을 사용해서 만들어진 알고리즘

d. 비결정론적 알고리즘

결과가 상항에 따라 달라질 수 있는 연산을 사용해서 만들어진 알고리즘

• 지정된 연산 결과의 집합 중에서
  하나를 선택할 수 있도록 허용

가) 비결정론적 알고리즘에 추가된 연산

• choices(s): 집한 S의 원소 중 최선의 하나를 임의로 선택

  • x = choice(1....m)

• failure: 알고리즘이 실패로 끝났음을 알림

• success: 알고리즘이 성공적으로 끝났음을 알림

---

4. 클래스 P와 클래스 NP

a. 클래스 P

결정론적 알고리즘을 이용하여 다항 시간에
해결할 수 있는 모든 판정 문제의 집합

• 쉬운 문제들의 판정 문제 버전을 원소로 갖는 집합

b. 클래스 NP

비결정론적 알고리즘을 이용하여 다항 시간에
해결할 수 있는 모든 판정 문제의 집합

c. P와 NP의 관계

• $P \subseteq NP$

• $P \neq NP$ ?

  • 클래스 NP에서 클래스 P를 뺀 여집합이 공집합인가?
    • $C = NP - P$ -> $C = \emptyset$ ?

d. 문제의 변환

문제 B에 대한 알고리즘으로 문제 A를 풀수 있을 때,
문제 A를 문제 B로 변환할 수있다고 표현한다.

• 문제 A의 입력과 출력을 문제 B의 입력과 출력 형태로 바꿀 수 있고,
  여기에 문제 B를 위한 알고리즘을 적용함으로써 해결할 수 있다는 의미

e. 완전 문제란?

어떤 부류(클래스 P, 클래스 NP)에 속하는 모든 문제가
그 부류에 속하는 어떤 문제 R로 다항식 변환이 가능하다면,
문제 R은 그 부류의 완전 문제다.

• 해당 부류의 모든 문제를 대표하게 된다.
• 해당 부류에서 가장 어려운 문제로 간주된다.

f. 하드 문제란?

어떤 부류에 속하는 모든 문제가
어떤 문제 R로 다항식 변환이 가능하다면,
문제 R은 그 부류의 하드 문제다.

• 문제 R이 그 부류에 속한다는 조건이 없다.

---

5. NP-완전성의 증명

a. 증명 과정

• 이미 NP-완전이라고 알려진 문제가 해당 문제로 다항식 시간 변환됨을 보인다.
• 비결정론적 다항식 시간 알고리즘이 존재함을 보인다.

Cook이 최초로 CNF 만족성 문제가 NP-완전임을 증명했다.

• CNF 만족성 문제 $\propto$ $L_1$ 문제라면,
  • $L_1$이 NP-하드 문제
    
    
• $L_1$을 해결하는 비결정론적 다항식 시간 알고리즘이 있음을 보인다면,
  • $L_1$이 NP-완전 문제

---