알고리즘 - 21 P와 NP 문제

문제의 종류

1. 문제의 종류란

2. 현실적인 시간의 문제

3. 결정 문제와 최적화 문제

 

문제의 종료

 

해결 가능성 여부

- 풀수 없는 문제들

 현실적인 시간에 풀수 없는 문제들 -> 주어진 시간 범위에서 근사해를 구하는것이 목표

- 풀수 있는 문제들

 현실적인 시간에 풀수 있는 문제들 -> 지금까지 배운 문제들

 

 

풀수 없는 문제 unsolvable/undecidable

- 정지 문제

- 힐베리트의 10번째 문제

 

풀수 있는 문제 solvable/decidable

- 최소 신장 트리 문제, 최단 거리 문제(현실적인 시간 내에 풀수 있는 문제)

- Presburge 산술, NP-완비 (현실적인 시간 내 풀수 없는 문제)

 

 

현실적인 시간의 의미

- 다항식 시간의 의미 : 입력 크기가 n일경우 그 문제를 해결하는데 n의 다항식에 비례하는 시간이 걸릴 경우

  ex. 3 n ^ k + 5 n ^(k-1) + ..., n^k log n

- 비다항식 시간의 예시

 지수 시간 - ex : 2^n

 계승 시간 - ex : n!

 

 

요구하는 대답의 종류에 따른 문제 분류

- 결정 문제(판정문제) : yes or no의 대답을 요구하는 문제

- 최적화 문제 : 가장 좋은 해를 요구하는 문제

 

 

ex. 최단 거리 문제의 경우

- 결정 문제 : 정점 u에서 정점 v로 가는 길이 100이하인 경로가 존재하는가?

- 최적화 문제 : 정점 u에서 정점 v로 가는 최단 경로의 길이는 얼마인가?

 

 

 

NP-완비 이론의 전개를 쉽게하기 위해 yes/no(결정 문제)만을 대상으로 함

- 최적화 문제 -> 결정 문제로 바꿈

- 최적화 문제는 결정 문제보다 대답이 쉽지 않으므로 결정 문제가 어렵다면 최적화 문제도 어렵다고 할 수 있음

 

 

ex. TSP 문제 (Traveling Sales man Problem)

- n 개의 도시를 모두 방문하고 돌아오는 최단 거리를 구하라 (최적화 문제)

=> n개의 도시를 모두 방문하고 돌아오는 거리 K이하인 경로가 존재하는가? (결정 문제)

 

YES/No 문제는 다른말로 결정 문제(Decision Problem)라고 불림

- 어떤 문제를 다항식 시간에 결정 할 수 있으면 현실적인 시간에 풀 수 있음 (Tractable)

- 다항식 시간에 결정할 수 없으면 현실적인 시간에 풀 수 없음 (Intractable)

 

 

 

NP-완비(NP-Complete)

1. 다항식 시간에 해결할 수 있는 알고리즘은 발견된 바 없음

2. 다항식 시간에 해결 불가능하다고 증명된 것도 아님

3. 수천 수만의 NP-완비 문제중 단 하나라도 다항시간에 해결되면 모든 NP-완비 문제가 한번에 다항식 시간에 해결되는 논리적 연결 체계를 가지고 있음

 

 

NP군의 의미(NP : Nondeterministric Polynomial)

P 문제

- P : 다항식 시간에 해결할 수 있는 문제들의 군

- 지금까지 배운 문제는 모두 P 군

- 다항식 시간 내에서 더 적은 시간을 소요하는 알고리즘을 개발하는데 초점이 맞추어져 있음

 

NP 문제

- NP : 다항식 시간에 해결할 수 없는 문제군(Non-Polynomial)이 아님

- Nondeterministric Polynomial -> 비결정론적 다항식 시간에 해결할 수 있는 문제군

 

 

P와 NP의 가능한 두가지 포함 관계

- 모든 P군의 문제는 NP군에 속함

- P = NP ? NP - P = 공집합?

 

비결정론적 다항식 시간의 의미

- 임의의 그래프와 두 정점 S, F가 주어질 때, 정점 S에서 출발해서 정점 F에 이르는 경로가 존재하는지 알아보는 알고리즘을 개발하려는 경우

- 어디로가야 유리한지에 대한 정보가 없는 경우 최악의 경우 각 정점에서 두가지 씩 시도해 보아야 함

- 간선을 하나 따라가 보는 것을 1만큼 든다고 하는 경우

 -> 결정론적으로 말하면 최악의 경우 6의 시간 소요, 비결정론으로 말하면 2의 시간이 소요

=> 답을 구하는 과정에 시행착오는 고려하지 않고 그런 경로가 존재한다면 그 경로를 따라 F에 이르는데 걸리는 시간을 을 의미

 

변환

- 의미 : 변환(Reduction)은 NP-완비 이론의 논리 체계를 구성하는 핵심 원리

- 가정 결정문제 A가 다항식 시간에 해결가능한지를 알고 싶은데, 다항식 시간에 해결가능한 결정 문제 B를 이미 알고있다고 가정함

 

 

 

다항식 시간 변환

- 문제 A의 사례 alpha를 문제 B의 사례 beta로 바꾸되 아래의 성질을 만족하면 Polynomial - Time Reduction 이라 하고, 이를 alpha <=_p beta로 표기함

1. 변환은 다항식 시간에 이루어짐

2. 두 사례의 답은 일치함

 

문제 A를 푸는 알고리즘

1. 문제 A의 사례 alpha를 다항식 시간에 문제 B의 사례 beta로 변환

2. 변환된 사례 beta를 문제 B를 푸는 알고리즘을 이용하여 품

3. 사례 beta의 답이 yes이면 사례 alpha의 답은 yes, No이면 사례 alpha의 답은 no

=> 문제 B가 쉬운 문제라면 문제 A도 쉬운 문제임

 

변환의 예

해밀토니안 싸이클 Hamiltonian Cycle

- 그래프의 모든 정점을 한번씩만 방문하고 출발점으로 돌아오는 경로

- 입력 : 무방향 그래프 G = (V, E)

- 질문 : G에 해밀토니안 싸이클이 존재하는가? => 결정 문제

 

순회 세일즈맨 문제, 여행자 문제(Trabeling Salesman Problem : TSP)

- 가중치 있는 완전 그래프에서 길이가 가장 짧은 해밀토니안 싸이클의 길이를 찾는 문제

- 입력 : 양의 가중치를 갖는 무방향 완전 그래프 G = (V, E), 양의 실수 K

- 질문 : G에 길이가 K이하인 해밀토니안 싸이클이 존재하는가? => 결정 문제

 

1. 해밀토니안 싸이클 문제의 instance(사례) alpha를 아래와 같이 TSP 문제의 instance beta로 다항식 시간에 변환함

1. 사례 alpha가 해밀토니안 싸이클을 가짐

2. 사례 beta가 길이 4이하인 해밀토니안 싸이클을 가짐(그래프의 크기가 n이면 4대신 n)