algo_lec13

Today's Topics

• P vs NP
• Problem transformation
• NP-complete
• NP-complete example
• NP-hard

---

P, NP

• A polynomial-time non-deterministic algorithm is a non-deterministic algorithm whose verification stage is a polynomial-time algorithm.
• NP is the set of all decision problems that can be solved by polynomial-time non-deterministic algorithms.
• Every problem in P is also in NP. (P ⊆ NP)
• Most decision problems discussed (e.g., TSP, 0-1 Knapsack, Hamiltonian Cycle) are in NP.
• P는 빨리 풀 수 있는 문제이고, NP는 빨리 확인할 수 있는 문제입니다.

 

• 비결정적 다항 시간 알고리즘이란, 정답을 추측하고 그 정답이 맞는지 다항 시간 내에 확인할 수 있는 알고리.
• NP는 이러한 알고리즘으로 다항 시간 안에 검증 가능한 결정 문제들의 집합.
• P는 다항 시간 안에 직접 해결 가능한 문제들의 집합.
• 따라서 모든 P 문제는 NP에 속합니다. (P ⊆ NP)
• 우리가 다루는 대표적인 결정 문제들(TSP, 0-1 배낭, 해밀토니안 사이클 등)은 모두 NP에 속함.
• 요약하면, P는 문제를 빨리 ‘풀 수 있는’ 것이고, NP는 정답을 빨리 ‘확인할 수 있는’ 것.

---

 

P vs NP

• 현재까지 NP에 속하지만 P에 속하지 않는 문제가 있는지 아무도 증명하지 못함.• 핵심 질문: P = NP인가?
    - P ≠ NP를 증명하려면, NP에 속하지만 P에 속하지 않는 문제 하나를 찾아야 합니다.
    - P = NP를 증명하려면, NP에 있는 모든 문제에 대해 다항 시간 알고리즘을 제시해야 합니다.
• 이는 클레이 수학연구소의 밀레니엄 문제 중 하나입니다.

---

Problem Transformation

(문제 변환 또는 환원)

• 문제 A를 문제 B로 바꿔서, B에 대한 알고리즘으로 A를 해결하는 방법.
1. 문제 A의 입력을 문제 B의 입력으로 변환 (transform)
2. B 알고리즘 실행
3. B의 출력을 A의 출력으로 다시 변환

• 예시:
    A: 부분집합의 합이 K가 되는 집합을 찾는 문제
    B: 두 부분집합의 합이 같은 경우 찾기
    → 집합에 특정 값을 추가하여 변환 가능.

---

Polynomial Transformation (or reduction)

(다항 시간 변환)

1. 변환 함수 T가 다항 시간 내에 계산 가능하고,
2. 모든 입력 x에 대해 문제 A의 정답과 문제 B의 정답이 일치하면,

→ 문제 A는 문제 B로 다항 시간 변환 가능하다고 함: A ∝ B

---

NP-complete

(NP-완전 문제)

현실적인 시간엔 풀 수 없다 추정되면서 서로 강력한 논리적 연관성을 가진 특이한 문제들.

 

• A problem A is polynomially transformable to B if there is a polynomial transformation from A to B.
• Then, we write A ∝ B. 
• 문제 A를 문제 B로 다항 시간 문제 변환 가능

• 문제 A가 NP이고, 모든 NP 문제가 A로 다항 시간 내에 변환 가능하면, A는 NP-complete 문제.

• NP-complete 문제 중 하나라도 다항 시간 알고리즘이 존재한다면, P = NP가 됩니다.

• 대표적으로 CNF 만족 문제(CNF-SAT)가 최초의 NP-complete 문제로 Cook이 1971년에 증명함 (Cook-Levin 정리)

• To show that a problem P' is in NP-complete,
  1. P' is in NP
     • 문제 P′에 대한 해답이 주어졌을 때, 그 해답이 다항 시간 내에 검증 가능함을 보이면 됨.
  2. Choose a known NP-complete problem P and then reduce P to P'
     • 이미 NP-complete임이 알려진 문제 P를 고르고,
     • 문제 P를 문제 P′로 다항 시간 내에 환원(Reduction).
       • 문제 P의 입력을 문제 P′의 입력으로 변환하는 알고리즘이 다항 시간 내에 존재함을 보이면 됨.
       • 이 과정을 통해 "문제 P′가 적어도 문제 P만큼 어렵다"는 것을 의미.

---

Cook's Theorem

모든 NP 문제는 다항 시간 내에 CNF-SAT 문제로 환원 가능하다.
즉, CNF-SAT 문제는 NP-complete 문제이다.

---

NP-complete Example: TSP

• TSP(Traveling Salesman Problem)가 NP-complete임을 보이기 위한 절차:
    (i) TSP는 NP에 속함
    (ii) NP-complete 문제인 Hamiltonian Circuit(HC)으로부터 TSP로 다항 시간 변환 가능함을 보임. HC ∝ TSP

 

1. 문제 정의

 

해밀토니안 사이클 문제 (HC: Hamiltonian Circuit)

• 입력: 무방향 그래프 G=(V,E)
• 질문: 그래프 G에는 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 사이클이 존재하는가?

외판원 문제 (TSP: Traveling Salesman Problem)

• 입력: 가중치가 부여된 그래프 G_W=(V,E′), 정수 k
• 질문: 모든 정점을 한 번씩 방문하고 다시 시작점으로 돌아오는 총 경로 길이 ≤ k 인 투어(tour)가 존재하는가?

---

2. 문제 변환 (HC → TSP)

 

아이디어:

• HC 문제를 TSP 문제로 바꾸려면, 가중치 그래프 G_W*를 새로 만들어야 함

변환 방법:

1. 모든 정점쌍 (u, v) 에 대해 간선을 추가해 완전 그래프를 만든다.
2. 간선의 가중치를 다음과 같이 정의한다:
   • w(u,v)=1 if (u,v) ∈ E → 원래 HC 그래프에 존재했던 간선
   • w(u,v)=2 if (u,v) ∉ E → 없는 간선은 일부러 "비싸게" 만든다

→ 이렇게 하면, HC의 경로만이 총 비용이 정점 개수 n인 투어가 됨

---

3. 논리 관계

• 만약 G에 Hamiltonian Circuit(HCP)이 있다면,
  G_W에는 길이 n인 투어가 존재한다. (모든 간선의 가중치가 1인 경우)
• 반대로 G_W에 길이 n인 투어가 존재한다면,
  그것은 G에서 실제로 존재하는 간선만으로 이루어진 경로 → G에 해밀토니안 사이클이 있다는 뜻.

---

4. 시간 복잡도

• 이 변환 과정은 각 정점쌍을 한 번씩 검사하면 되므로,
  • 시간 복잡도는 O(V²) 또는 O(VE) 수준
  • 따라서 Polynomial Time 내에 변환 가능함

---

5. 결론

이 슬라이드는 HC 문제를 다항 시간 내에 TSP 문제로 환원할 수 있음을 보여주며,
TSP가 NP-complete임을 보이는 핵심 절차 중 하나.

---

Prime Number Problem

정수 n(>=2) 은, n과 서로소인 모든 정수 a에 대해 다음식이 성립할 때만 소수이며, 그렇지 않으면 합성수이다

If (a,n) = 1, then (X+a)^n = X^n+a (mod n)

if and only if n is prime.

• "n이 소수인가?" → 결정 문제, 이는 P에 속함 (AKS 소수 판별 알고리즘, 2004년)
• 하지만 소인수분해(prime factorization)는 여전히 매우 어려움 → NP에 속하지만 NP-complete인지 불분명
• 소수가 아닌지를 묻는 문제(factorization problem)는 NP에 속하고, 소수 문제는 co-NP에 속함

NP (Nondeterministic Polynomial time)
정답을 추측하면 다항 시간 내에 "검증"할 수 있는 문제들의 집합
예: "이 수는 소수가 아니다" → 어떤 인수를 제시해주면 금방 확인 가능

co-NP
NP의 반대 개념 "정답이 '아니다'일 때 쉽게 검증되는 문제"
예: "이 수는 소수이다" → 틀렸다는 걸 쉽게 증명할 수는 없음.


[소수(primality) vs 소수가 아님(factorization)]
1. 소수가 아닌지를 묻는 문제
“이 수는 소수가 아니다”라는 것을 증명하려면? → 어떤 약수(인수) 하나만 제시하면 됨 (예: 15는 3×5니까 소수 아님)
후보(인수)를 추측한 다음, 나눠보기만 하면 되므로 이 문제는 NP에 속함

2. 소수인지를 묻는 문제
“이 수는 소수이다”를 어떻게 증명할까? → 인수분해를 할 수 없다는 걸 보이는 건 어려움.
'소수가 아니다'는 쉽게 증명되지만, '소수다'는 반례가 없음을 보여줘야 해서 더 어려움.
→ 그래서 이 문제는 co-NP에 속한다고 분류함
(즉, “소수가 아니다”라는 주장이 NP에 속하면, “소수다”는 co-NP에 속하게 됨)

---

NP-hard

• NP-hard는 NP-complete보다 더 넓은 개념으로, NP-complete 문제만큼 또는 그보다 더 어려운 문제들을 포함합니다.
• NP-complete ∈ NP-hard
• NP-hard 문제 중 하나라도 다항 시간에 풀 수 있다면 NP = P가 성립함

If a polynomial time algorithm exists for any NP-hard problem,
you can easily solve the NP-complete problem in polynomial time.

 

• 최적화 문제나 계산 문제도 포함됨.

---

How to Handle NP-hard Problems

• backtracking algorithm or branch-and-bound algorithm 사용 → 모든 경우 탐색하되, 불필요한 경우 제거하는 방식
• approximation algorithm 사용 → 최적해는 아니지만 충분히 좋은 해를 빠르게 구함