[계산이론](28)[NP-Complete]

NP-complete

NP이고 (모든 NP문제) $\le_p$ NPc 인 NPc
만약 NPc 중 하나만 poly 알고리즘이 나오면,
모든 NP문제는 poly 알고리즘이 있다는 것이 증명된다.

• $\le_p$ : 다항시간 환원 가능
  다항시간 함수 $\exists f: \ \sum^* \rightarrow \sum^*$일때,
  w, $w \in A \Leftrightarrow f(w) \in B$이면 $A \le_p B$라고 한다.
  -> w가 accept면 reduce된 w가 accept

만약 A가 B로 다항시간 환원 가능이고 B가 P에 속하면 A도 P
    $A\le_pB \ & \ B\in P \Rightarrow A \in P$

 

만약 B가 NPc이고 B가 NP인 C로 다항시간 환원 가능이면 C도 NPc이다
    B is NP-complete & C is NP & $B\le_p C \Rightarrow$ C is NP-complete
-> 이걸로 하나의 NPc만 있으면 점차 늘려나갈 수 있다.

 

SAT

최초의 NP-complete 알고리즘
조합을 통해 주어진 논리식을 참으로 만들 수 있는가?

• SAT is NP
  바로 poly verifier가 있다!
      조합 중 하나인 c를 바로 논리식에 집어넣으면 된다
      O(n)의 시간복잡도
• SAT is NP-complete
  cook-levin 정리
  -> 모든 TM의 동작 자체를 논리식으로 표현해보자
  NTM의 n^k 실행 과정을 n^k by n^k 짜리 행렬로 표현하고
      가로: tape 공간, 세로: step
  이렇게 만든 거대한 논리식의 결과 = NTM의 결과
  따라서 모든 NP문제는 SAT문제로 바꿀 수 있다.
  -> SAT is NP-complete
  
  
• 3SAT
  $\phi = (x_1 \lor \neg x_2 \lor x_3) \land (x_2 \lor x_3 \lor \neg x_4) \land (\dots)$ 꼴의 식을 참으로 만들 수 있는가?k개의 노드가 fully connected된 subgraph가 존재하는가?

 

k-CLIQUE

• CLIQUE is NP
  • subgraph c가 주어졌을 때 poly verifier가 있다.
    1. c가 G에서 k개의 노드를 가진 subgraph인지 테스트
    2. G에 c의 모든 E를 가지고 있는지 테스트
       대략 O(n+n^2) 정도?
  • poly NTM이 존재한다
    1. G의 subgraph를 nodeterministic하게 선택함
    2. 각 노드를 연결하는 모든 E가 있는지 판정
       대략 O(n^2) 정도?
• CLIQUE is NP-complete
  $3SAT \le_p CLIQUE$이므로, CLIGUE도 NP-complete

 

Vertex-Cover

최소한의 V를 선택해 모든 E를 커버할 수 있는가?
이것도 NP-complete이다

• Vertex-Cover is NP
  poly verifier가 존재한다
      1. c에 대해 이게 유효한 그래프인지 판정
      2. c에 있는 노드들에 연결된 E를 합쳤을 때 원본 그래프의 E가 전부 커버되나 확인
      대략 O(V+E) = O(n^2)정도
• Vertex-Cover is NP-complete
      $CLIQUE \le_p VERTEX\text{-}COVER$이므로
      Vertex-Cover는 NP-complete

P vs NP

P ⊆ NP는 확실하다
P ≠ EXPTIME도 증명되어 있다.

 

그러나, P = NP인지는 아직 모름
    P로 풀 수 있는 NPc가 있는지도 못찾음
    NP로밖에 풀 수 있는 NP도 못찾음
P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME
    여기 중 어디서 =이 빠졌는지 모름

 

참고
    PSPACE: poly 메모리, 무한 시간
    NPSPACE: poly 메모리, nondeterminisim, 무한 시간
    EXPTIME: 메모리 무한, exp 시간