L16 - NP-Completeness (1)

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

Motivation

 

외판원 순환 문제 (TSP : Travelling salesman problem)

 

 

ex. A, B, C, D, A 순서

 

 

모든 정점을 방문하고 시작 정점으로 돌아오는 최단 경로를 찾는 문제인데

 

Brute-force 방식으로 n개의 정점의 모든 permutation(순열)을 조사해야함

 

=> O(n!)

 

TSP 문제를 다항시간에 푸는 알고리즘이 존재할까?

 

이론상 불가능함

 

Types of Problems

 

현실적인 시간 -> Polynomial Time

 

 

Tractable Problem : 입력 n에 대하여 푸는데 걸리는 시간이 다항 함수 f(n) 으로 표현 되는 문제

다항 함수 f(n)

 

Intractable Problem: 다항 시간안에 풀 수 없는 문제

=> Θ(2^n) 이나 Θ(n!) 같은 것 들은 Intractable Problem

 

 

 

Decision Problem / Optimization Problem

 

풀 수 있는 문제의 분류 

 

• 결정 문제 (Decision Problem)
  
  
  • Yes / No 의 대답을 요구하는 문제
    
    
  • ex. 정점 u -> v 로 가는 길이 100 이하인 경로가 존재하는가?
    
    
• 최적화 문제 (Optimization Problem)
  
  
  • 가장 좋은 해를 요구하는 문제
    
    
  • ex. 정점 u -> v 로 가는 최단 경로의 길이는 얼마인가?

 

NP-Completeness 이론은 결정 문제를 대상으로 함

=> 최적화 문제는 대응되는 결정 문제로 변환하여 분석
(결정 문제가 어려우면 대응되는 최적화 문제도 어려움)

 

P, NP

 

P : 다항 시간에 풀 수 있는 Yes/No 문제 집합

=> 지금까지 다룬 알고리즘 포스팅의 모든 문제는 P 문제였음

(Sorting, Selection, MST, SSSP, String Matching ...)

 

NP : 비결정론적 (Non-deterministic)으로 다항 시간에 풀 수 있는 Yes/No 문제 집합

=> Non-Polynomial 이 아님!!

 

Deterministic / Non-deterministic

 

 

 

정점 S에서 F로 가는 경로가 존재하는지 확인하는 문제를

 

결정론적으로 푼다면 모든 경로를 다 가보는 수 밖에 없음

 

=> 각 직선을 따라가는데 1만큼 걸린다면, 최악의 경우 14만큼의 시간이 걸림

 

결정론적 알고리즘은 하나의 상태에서 한 가지 결정만 내릴 수 있음

 

비결정론적 관점에서는 3의 시간이 걸림

 

=> F까지 경로가 존재한다면, 그 경로 길이와 동일한 시간이 걸림
(양쪽 방향으로 동시에 갈 수 있으므로)

 

비결정론적 알고리즘은 하나의 상태에서 모든 결정을 동시에 내릴 수 있음

 

 

아까 NP 문제는 비결정론적 다항 시간 문제라고 했는데

 

이는 결정론적으로 다항시간에 정답 검증이 가능한 문제를 의미함

 

=> S에서 오른쪽, 왼쪽, 왼쪽으로 갔을 때 F가 나오나?

 

P = NP ?

 

 

컴퓨터 공학 분야에서 아직 풀리지 않은 난제들 중 하나임..

 

일단 모든 P문제는 NP문제임

=> P ⊆ NP

 

검증하는게 푸는 것 보다 쉬움

(풀 줄 알면 검증도 할 수 있으니 P ⊆ NP)

 

그런데

 

NP - P = ∅ 인지는 검증되지 않음

 

=> NP 문제이지만 P문제는 아닌 그런 문제가 존재하는지 모름

 

Polynomial-time Reduction

 

 

문제 A의 입력 α를 문제 B의 입력 β로 바꾸되 

 

1. 변환은 다항시간에 이뤄진다

 

2. 두 사례의 답이 일치한다

 

를 만족하면 다항시간 변환 이라 하고, 이를 α ≤p β 라고 표기함

 

Example of Reduction

 

Hamiltonian cycle problem -> TSP (Traveling Salesman Problem)

 

무향 그래프 G에 hamiltonian cycle이 존재하는가?

 

라는 문제를 변환하여

 

가중치를 갖는 무향 완전 그래프 G에 길이가 K 이하인 hamiltonian cycle이 존재하는가? 로 해결할 수 있음

(완전 그래프에서는 hamiltonian cycle이 항상 존재함)

 

 

HAM-CYCLE의 입력 G를 TSP의 입력 G'로 변환

 

• G의 모든 간선의 가중치를 1로 설정하고
  
  
• 없는 간선은 생성하여 가중치를 무한대로 설정
  
  
• 변환 과정에서 정점의 수가 n일 때, O(n^2)라는 다항시간 만큼이 필요함

 

K = n인 TSP 문제의 정답 = HAM-CYCLE의 정답

 

Implication of Poly-time Reduction

 

문제 A를 풀기 위해 문제 B를 푸는 알고리즘을 사용

 

 

 

문제 B를 쉽게 푸는 알고리즘이 있다면 => 문제 A도 쉽게 풀 수 있음

 

문제 B를 쉽게 푸는 알고리즘이 없어도 => 문제 A를 쉽게 푸는 알고리즘은 존재 가능

 

즉, 문제 B가 문제 A보다 쉽지 않다

 

NP-Hard, NP-Complete

 

 

 

NP-Hard

 

모든 NP 문제에서 다항시간 변환이 가능한 문제의 집합

 

=> 즉, 모든 NP 문제를 문제 A로 다항시간 변환 가능하면 문제 A를 NP-Hard 문제라고함

 

NP-Hard에는 yes/no 문제 뿐만 아니라 최적화 문제도 포함

 

NP-Complete

 

NP-Hard 이면서 NP인 문제