15. Problem Classes - P, NP, NPC

Complexity Classes

세상에는 이상한 문제가 많습니다. 사람들은 그런 문제들의 난이도를 분류해서 구분하고 있습니다. P냐 NP냐 그런 것들이 다 문제의 난이도를 나타내는 말입니다.

 

한번 그런 문제 중 하나인 한 붓 그리기를 생각해 봅시다.

 

• 그래프에 있는 모든 edge를 한 번만 사용하는 한 붓 그리기가 가능할까요?
• 그래프에 있는 모든 vertex를 한번만 방문하는 한 붓 그리기가 가능할까요?
• 그래프에 있는 모든 vertex를 한번만 방문하되, edge의 weight의 합이 B를 넘어가지 않게 한 붓 그리기가 가능할까요?

 

위의 각 문제는 각각 Euler Tour, Hamiltonian Circuit, Traveling Salesman이라고 불리는 문제입니다. 통상적으로 Euler Tour 문제는 Easy, Hamiltonian Circuit과 Traveling Salesman 문제는 Hard하다고 평가받습니다.

 

또 다른 문제인 Shortest path를 찾는 문제와 Logest path를 찾는 문제가 있습니다. Shortest path는 우리가 공부했듯이 Easy하지만 Logest path를 찾는 문제는 Hard하다고 평가받고 있습니다.

 

문제의 난이도를 구별하는 기준이 무엇일까요?

 

우리는 모든 계산 문제(computational problem)를 풀 수 있을까요?

우리는 계산 문제를 효율적으로 풀 수 있을까요?

 

모두 대답은 NO 입니다.

 

Halting Problem

1900년도에 Halting씨는 "수학에는 모순이 없다."는 것을 증명하고 싶었습니다. Halting씨의 생각은 공리가 있다면 수학은 그 부분에서 모순을 가지지 않는다는 것이었습니다.

 

이 명제는 1936년 Alan Turing에 의해 틀리게 됩니다. Alan Turing은 logical해도 풀리지 않는 문제가 있음을 보임으로써 수학의 불완전성을 증명하게 됩니다. 매우 간단한 함수 2개에 의해 증명이 됩니다.

Halting 함수는 어떤 함수가 무한하게 동작하면 false를 아니면 true를 반환하는 함수입니다. Arbitrary program g는 Halting 함수에 자신을 넣어서 Halting 함수가 true를 반환하면 무한한 loop를 돌게 됩니다.

 

두 함수 모두 논리적으로 오류가 없음에도 실행되지 않는 것을 보임으로써 수학의 불완전성을 증명하게 됩니다. 이를 통해 우리는 계산 가능한 모든 문제를 풀 수 없다는 것을 알 수 있습니다.

 

Types of problems

문제의 종류는 여러 가지이겠지만 보통 다음의 3가지 영역으로 분류할 수 있습니다.

• Optimization problem
  ex) shortest path 찾기
• Decision problem
  ex) s에서 t로 k hop만에 갈 수 있는 경로가 있는가?
• Search problem
  ex) s에서 t로 k hop 이하로 갈 수 있는 경로 찾기

 

Hardness of problems

다음의 구분을 하고 있습니다. 지금은 참고만 합니다.

Hardness of problems

Problem classes

그런데 문제의 어려움은 어떻게 비교하는 것일까요? Reduction이라는 개념을 사용해 구분하게 됩니다.

 

Reduction

Problem A와 B가 있습니다. A는 잘 모르지만 B는 해결하는 방법을 알고 있습니다.

 

우리가 만약 $x_A$를 잘 조정해 $x_B$를 만들 수 있고,

$f(x_A)$를 이용해 $B(f(x_A))$의 결과를 얻어서 잘 조정해 $A(x_A)$를 얻을 수 있다면

 

A는 B에 reducible하다고 말합니다. 그림으로 나타내면 다음과 같습니다.

 

한마디로 잘 알고 있는 문제(B)를 이용해 모르는 문제(A)를 해결할 수 있다면 A는 해결 가능한 문제가 되며 B 문제로 reduction(환원)되는 것입니다.

A is reducible to B if A ≤ B

만약 $T(f(x_A))$ ≤ $T_B(n)$을 만족한다면 다음의 결과도 얻을 수 있습니다.

• B는 적어도 A만큼 어려운 문제가 됩니다.
• A는 $T_B(n)$ 안에 해결할 수 있는 문제가 됩니다.

*Polynomial-time reduction: $T(f(x_A))$ in $P$

 

Problem classes: P vs NP

P는 polynomial time에 deterministic한 문제입니다. 자세히 설명하면 polynomial time안에 deterministic한 튜링 머신에 의해서 해결이 가능한 decision problem을 말합니다.

 

반대로 NP는 polynominal time에 nondeterministic한 문제입니다. 자세히 설명하면 polynomial time안에 non-deterministic한 튜링 머신에 의해 해결이 가능한 decision problem을 말합니다. Deterministic 튜링 머신에 의해 polynomial time안에 verifiable하기는 합니다.

 

NP-hard vs NP-complete

NP 중에서도 급이 나뉘게 됩니다.

 

NP-hard

NP의 모든 문제가 A로 polynomial-time reduction을 한다면 A는 NP-hard입니다. NP보다 어려운 문제입니다.

 

NP-complete

A가 NP(polynomial time에 해결이 안됨)이면서 NP-hard(NP보다 어려운가)이면 A는 NP-complete입니다. NP에서 가장 어려운 문제입니다.

P, NP, NP-Hard, NP-Complete

 

NP-complete

Cook-Levin Theorem이 있습니다. 어떤 문제도 circuit으로 reducable하다는 주장입니다. NP-complete이며 다른 문제와 다음의 관계를 가지고 있습니다.

Relation

 

NP - P - co-NP

co-NP는 NP와 같은 문제를 반대의 state로 나타낸 문제입니다. 가령 NP가 "yes" instance를 주고 yes임을 보이는 문제라면, co-NP는 "no" instance를 주고 no임을 보이는 문제가 되는 것입니다.

co-NP 분포

 

Computational Problems

앞에서 봤던 문제의 class는 무엇이었을까요?

 

• 그래프에 있는 모든 edge를 한 번만 사용하는 한 붓 그리기가 가능할까요?
  P
• 그래프에 있는 모든 vertex를 한번만 방문하는 한 붓 그리기가 가능할까요?
  NP-complete
• 그래프에 있는 모든 vertex를 한번만 방문하되, edge의 weight의 합이 B를 넘어가지 않게 한 붓 그리기가 가능할까요?
  NP-complete

 

Shortest path(=P) vs Logest path(=NP-complete)

 

Hamiltonian Circuit & TSP

• Hamiltonian circuit
  모든 vertices를 도는 Elementary circuit이 있니?
• Traveling salesman
  모든 도시를 방문하는데 total length가 B인 경우가 있니?

Hamiltonian circuit이 NP-complete라는 사실을 이용해 TSP가 NP-complete임을 보여봅시다.

 

이를 위해서는 TSP가 verifiable in P(1)인지, NP-hardness(2)인지 확인해야 합니다.

 

(1) Path가 주어지면, cost가 B인지 polynomial time에 확인할 수 있습니다.

(2) NP-hardness는 reduction을 수행해 보면 알 수 있습니다.

TSP reduction

TSP는 Hamiltonian circuit만큼 어려운 문제가 되서 NP-hard임이 증명됩니다.

 

따라서 TSP는 NP-complete입니다.

 

How to deal with diffcult problems?

이런 어려운 문제는 어떻게 풀어야 할까요? 다음의 방법이 있습니다.

Approximation	Optimal에 근사한 solution 찾기
Randomization	Random 알고리즘 사용하기
Restriction	Input의 형태를 제한하기
Parameterization	Input의 parameter가 고정되는 경우 만들기
Heuristic	증명 없이 대부분의 경우에 잘 되는 방법 사용하기

 

*Example: 2 Approximation on TSP

MST를 구해서 테두리를 도는 방법으로 항상 Optimal solution의 2배를 넘지 않게 된다.