P vs NP

P: Polynomial, 아무리 어려워도 polynomial time내에 확실히 끝낼 수 있음

• O(n^k)
• sorting, Dijkstra, 최대공약수 등

NP: Non-deterministic Polynomial (보통 시간복잡도가 Exponential 형태인 애들)

• 입력 솔루션이 PT내에 맞다/틀리다 검증 가능한 문제 (대입해서 풀리는 정도?라고 이해하면 될까)
• NPC: NP(검증가능)면서 NP-Hard인애들 ⇒ 벤다이어그램 기준, NPC = NP ∩ NP-Hard
  • 대표 문제 21개가 있다
  • 대표 문제의 의미: NP 문제를 NPC로 매핑(in P.T.) → NPC 해결 → Output Mapping(in P.T.)
  • 달리 말하면 대표 문제로 매핑이 가능하다면 NP Hard라는 것을 증명할 수 있다 (NPC ∈ NP-Hard니까)

NPC 예시

Circuit-SAT(Satisfiability)

• 조합논리회로에서 입력에 따른 Output 예측 (0?, 1?)
• Input이 n개인 조합회로의 output을 예측하려면(output은 하나여야 함) Truth Table처럼 모두 해 보는데 2^n번 해야함
• O(2^n)

Traveling Salesman Problem(TSP)

• 모든 도시 찍고 home으로 돌아오기 (모든 Node는 연결돼있다 가정하는 듯) → dijkstra랑 비슷한데, 얘는 집으로 돌아오는 것 때문에 NP 문제임
• 노드 3개면 path(경우의 수) 2개, 노드가 네개면 path는 6개, 노드가 5개면 24개… ⇒ path의 개수는 (n-1)!임 ※ (n/e)^n < n! < n^n
• O(n^n)

Knapsack Problem

• 무게가 제한된 배낭에 무게와 가치가 제각각인 물건들을 넣는다고 할 때, 어떻게 넣는 것이 가장 효율적인가
• 기본적으로 n^n번 해봐야 한다. 물론 가방 무게가 제한적이므로 일부 Case는 배제시킬 수 있다