18~19장 Average-Case Complexity & Hardness Amplification

Average-Case Complexity & Hardness Amplification

이전 글에서는 다음 내용을 다루었다.

• $P, NP$
• Circuit Complexity
• $#P$, PP, Toda’s Theorem

이번 글에서는 그 흐름을 이어
Worst-case → Average-case 복잡도 전환을 다룬다.

---

1. Worst-case vs Average-case

Worst-case complexity

$ T(n) = \max_{x \in {0,1}^n} T(x) $

→ 가장 어려운 입력 기준

---

Average-case complexity

$ \mathbb{E}_{x \sim D}[T(x)] $

→ 입력 분포 $D$에서 평균 성능

---

핵심 차이

• Worst-case: 이론 중심
• Average-case: 현실 문제와 밀접

---

2. Average-case Hardness

문제는 다음 질문이다.

어떤 문제가 평균적으로도 어려운가?

---

정의 (평균 난이도)

함수 $f$가 평균적으로 어렵다는 것은

$ \Pr_{x \sim D}[A(x) = f(x)] \leq \frac{1}{2} + \epsilon $

즉

• 어떤 알고리즘도 높은 확률로 못 맞춤

---

3. Hardness Amplification

목표

약하게 어려운 문제 → 매우 어려운 문제로 강화

---

아이디어

함수 $f$가 약하게 어려울 때

새로운 함수 $g$를 만들어

$ g(x_1, ..., x_k) = f(x_1) \oplus f(x_2) \oplus ... \oplus f(x_k) $

---

결과

성공 확률 감소:

$ \left(\frac{1}{2} + \epsilon \right)^k $

→ 빠르게 $1/2$로 수렴

---

4. XOR Lemma

Hardness amplification의 핵심 정리

XOR Lemma

$ f $가 약하게 어렵다면
$ f^{\oplus k} $는 매우 어렵다.

---

의미

• 여러 번 결합하면
• 예측이 거의 불가능해짐

---

5. Error-Correcting Codes 연결

Hardness amplification은
Error-Correcting Code와 깊은 연결이 있다.

---

코드 변환

$ f(x) \rightarrow C(f)(x) $

여기서 $C$는 코드

---

특징

• 일부 오류 허용
• 전체 정보 복원 가능

---

복잡도 연결

• 작은 정확도 → 복구 가능
• 계산 어려움 유지

---

6. Worst-case → Average-case Reduction

핵심 목표:

최악의 경우 어려움 → 평균적으로도 어려움

---

구조

1. worst-case 문제 $f$
2. 변환 $g$
3. $g$는 average-case hard

---

결과

암호학에서 매우 중요

---

7. 암호학과의 연결

Average-case hardness는
암호학의 기반이다.

---

이유

암호는 다음을 요구한다:

• 대부분 입력에서 어려워야 함

---

예시

• One-way function
• Pseudorandom generator

---

8. 핵심 정리

1. Worst vs Average

$ \max $ vs $ \mathbb{E} $

---

2. Hardness amplification

$ f \rightarrow f^{\oplus k} $

---

3. XOR Lemma

난이도 강화 핵심 도구

---

4. Error-Correcting Code

복잡도 + 복원 능력 결합

---

정리

이번 글의 핵심:

1️⃣ 평균 난이도는 현실 문제의 핵심이다

2️⃣ Hardness amplification은 난이도를 강화한다

3️⃣ XOR Lemma는 핵심 이론이다