P,NP,NPC 문제

• 알고리즘을 풀다 보면 알고리즘의 유형을 정리하고 싶을 때가 많다.
• 이 문제를 어떤 알고리즘으로 풀면 좋을지, 내가 쓰고 싶은 알고리즘(동적 프로그래밍, 그리디)로 풀 수는 있는지, 아니면 아예 풀 수 없는 문제인지
• 그런 문제 분류를 좀 더 큰 그림에서 연구하는 학문을 계산 복잡도 이론이라 한다.

계산 복잡도 이론

• 각 문제를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제를 분류하고, 각 분류의 특성을 연구하는 학문이다.
• 여기서 말하는 복잡도는 시간 복잡도랑은 조금 다르다.
• 시간 복잡도는 알고리즘의 특성이다.
• 계산 복잡도는 해당 문제 특성이다.(문제를 풀 수 있는 빠른 알고리즘의 시간복잡도)

어려운 문제, 쉬운 문제

• 다항시간에 풀 수 있는 문제는 “쉽다”고 하고, 다항시간 알고리즘은 “빠르다” 고 한다.
• 다항시간에 풀 수 없는 문제는 어려운 문제들이다.
• 하지만 다항시간에 절대 못 풀 줄 알았는데, 나중에 방법을 찾을 수도 있으므로 섣불리 “어렵다”고 정해 놓은 문제는 없다.
• 그것보다는 “하~ 이 부분만 풀리면 다항식에 풀릴 것도 같은데, 방법은 아직 못 찾았네. 어쩌면 문제 특성상 다항식에 못 푸는 걸지도?” 라는 컨셉으로 모아놓은 문제들이 NPC(NP-완비) 이다.
• 즉, NPC 문제는 아직 쉬운지 어려운지도 결정하지 못한 문제들이다.

난이도의 비교

• A문제와 B문제 중 어떤 게 더 어려운지는 알기 어렵다.
  • 우리가 알고 있는 각 문제의 풀이가 가장 빠른 풀이인지는 영원히 알 수 없기 때문이다. (상수시간이라면 가능할지도)
• 문제 난이도 비교를 위해서 “환산” 을 이용한다.
• A문제를 B문제로 바꿔서(환산) 문제를 풀어 볼 수 있다.
  • 이 때 문제가 풀린다면, B문제는 A를 푸는 알고리즘 + A를 B로 환산하는 알고리즘 시간에 풀렸다는 말이다.
  • 즉 B문제는 A문제보다 빠르거나 같은 시간에 풀릴 수 밖에 없다.
  • A는 B 이상으로 어렵다는 결론을 낼 수 있다.

문제의 분류

• 알고리즘에서 자주 언급되는 문제군은 다항시간(Polynomial)을 기준으로 나뉜다.

P군(Polynomial problem)

• 상수 k에 대해 O(n^k)시간에 풀 수 있는 문제이다.
• 알고리즘을 풀 때 느린 알고리즘으로 치부하는 O(n^2), O(n^3)도 현실 세계에서 풀리긴 하는 다항시간이므로 “쉽다” 고 표현한다.

NP군(Non-deterministic Polynomial problem)

• 다항시간에 “검산” 할 수 있는 문제이다.
• 다항시간에 풀 수 없는지는 생각하지 않는다.

실생활에서 생각해본 예시

사람들이 환장하는 음료를 개발하기

• 음료 개발은 엄청나게 오래 걸릴 수 있지만, 어떤 음료가 출시되었을 때 사람들이 환장하는지 검증(검산)하는 건 쉽다.(매출을 보면 확인되지 않을까)
• 이렇게 검증은 쉽게 되는 문제는 NP 군이다.
• 음료 개발마저 쉽더라도, 검증이 쉽게 되는 건 동일하므로 여전히 NP 군이다.
• 음료 개발하는 게 쉽다면, 이 문제는 P문제이기도 하다.
• 여기서 모든 P문제는 NP문제라는 걸 알 수 있다. (개발하고 검증하면 되므로)

NP군의 특징

• 모든 P군 문제는 NP군에 속한다.
• 모든 NP 군이 P군에 속하는지는 아직 아는 사람이 없다.
  • P=NP? 문제라고 부른다.
  • 밀레니엄 7대 수학 난제이다.
  • 속하는지, 속하지 않는지, 아니면 그것마저 증명할 수 없는지 증명한 사람이 없다.
• 모든 NP군이 P 군에 속하는지를 증명하는 순간 P = NP 가 된다.
  • 지금까지 나온 P속하지 못한(다항 시간에 풀지 못한) NP문제들 모두 다항시간에 풀 방법이 있다는 말이므로, 이제 최선을 다해서 방법을 찾으면 된다.
  • 증명 전까지는 방법이 있는지 없는지도 모르는 상태다.

NPC군(NP-complete)

• 어떤 문제가 NP 문제이고, NP에 속하는 임의의 문제만큼 “어렵다” 면 이 문제는 NPC군에 속한다.
• 위 개념을 바탕으로 쉬운 말로 바꿔보자면 어떤 문제를 적당히 바꿔서(환산) 알려져 있는 NP군 문제 중 아무거나(P일수도, NP일수도, NPC일수도) 줘도 풀 수 있다면 이 문제는 NPC 군에 속한다.
• 보통은 P문제는 그냥 풀리므로, P에 속하지 않는 NP문제를 풀 수 있는지 확인을 해야 하고 증명 방법이 따로 있다고 한다.
• NPC는 간단하게 말하면 P가 아닌 “찐 NP” 정도로 말할 수 있을 것 같다.

NPC군의 특징

• NPC 군 중 한 문제만 다항 시간에 풀 수 있다면 모든 NPC 문제가 다항시간에 풀릴 수 있다.
  • 정의 자체가 다른 모든 NP문제들보다 어렵거나 같은 난이도의 문제이므로
• 대부분의 NP 문제는 P문제와 한끗차이이다.

NPC 문제를 다루는 개발자의 자세

• NPC 문제는 세계적 석학들이 수년간 연구했음에도 다항식으로 풀 방법을 찾지 못한 문제들이므로, 어떤 문제가 NPC 문제라는 걸 알았다면 답을 내려고 고민하기보다는 다른 방법을 찾는 게 낫다.(진짜 책에 이렇게 쓰여있음)
  • 근사 알고리즘을 찾아본다. (클라이언트랑 적당히 타협본다.)
  • 쉽게 풀리는 특수한 경우에만 문제를 푼다. (문제의 범위를 좁힌다.)
• 그러기 위해서는 어떤 문제가 안 풀린다 싶으면 “이거 혹시 NPC 문제?” 라고 의심해보고 확인해보는 것도 중요한 것 같다.
• 위의 타협들은 개발자 실력 문제가 아니라, 문제 자체의 문제이므로 당당해도 된다. (실수로 밤새서 풀어버리면 필즈상행)

P와 NP의 한 끗 차이

• 최단 단순경로(P) 와 최장 단순 경로(NPC)
• 오일러 경로(P) 와 해밀토니안 순환(NPC)
  • 오일러 경로는 모든 ‘간선’을 순환한다. (한붓 그리기)
  • 해밀토니안은 모든 ‘정점’을 순환한다.
• 2-CNF(P) 와 3-CNF(NPC)
  • 아직 공부가 필요하다.

---

더 공부해 볼 부분

• 유명한 NPC 문제 살펴보기
• CNF 와 SAT 살펴보기
• 알고리즘 책의 NPC임을 증명하는 부분 보기

출처

• 종만북 1권
• Introduction to Algorithms (3rd edition)