정의
BPP (Bounded‑error Probabilistic Polynomial time)는 확률적 알고리즘이 다항 시간 안에 동작하면서 오류 확률이 상수(보통 1/3) 이하인 경우에 결정할 수 있는 언어들의 집합이다. 정확히는, 입력 길이 $n$에 대해 다음을 만족하는 확률적 튜링 기계 $M$가 존재한다.
- 모든 입력 $x$에 대해, $M$는 다항 시간 $p(n)$ 이내에 실행된다.
- $x$가 언어에 속할 때, $M$가 “수락”할 확률이 최소 $2/3$이다.
- $x$가 언어에 속하지 않을 때, $M$가 “수락”할 확률이 최대 $1/3$이다.
오류 한계인 $1/3$은 임의의 상수 $0<\epsilon<1/2$ 로 교체 가능하며, 오류 확률을 줄이기 위해 독립적인 실행을 다수 수행한 뒤 다수결을 취하는 확률적 증폭(amplification) 기법이 존재한다.
어원
BPP는 영어 구문 Bounded‑error Probabilistic Polynomial time의 머리글자를 딴 약어이다. “Bounded‑error”는 허용 가능한 오류 확률이 상수 수준으로 제한됨을 의미한다.
주요 성질 및 관계
| 관계 | 설명 |
|---|---|
| $ \mathbf{P} \subseteq \mathbf{BPP} $ | 결정적 다항 시간 알고리즘은 오류가 0이므로 자동으로 BPP에 포함된다. |
| $ \mathbf{BPP} \subseteq \mathbf{PH} $ | 베르난데 라인하르트 등(1986)의 결과에 따라 BPP는 다항계층(Polynomial Hierarchy) 안에 있다. |
| $ \mathbf{BPP} \subseteq \mathbf{PSPACE} $ | 다항 공간을 사용하면 모든 확률적 다항시간 과정을 시뮬레이션 가능하다. |
| $ \mathbf{BPP} = \mathbf{P} $ (조건부) | 충분히 강한 난수성 가정(예: 낮은 회귀성 난수 생성기)이나 암호학적 가정(예: 일방향 함수 존재) 하에서는 BPP가 P와 동등하다는 결과가 존재한다. |
| $ \mathbf{BPP} \subseteq \mathbf{EXP} $ | 모든 BPP 언어는 지수 시간 내에 결정 가능하다. |
폐쇄성
- 연합(Union) 및 교집합(Intersection) 에 대해 닫혀 있다.
- 보수(Complement) 에 대해 닫혀 있다(오류 한계가 대칭적이기 때문).
- 다항 시간 투표(Polynomial‑time Turing reductions) 에 대해 닫혀 있다.
대표적인 BPP 알고리즘
| 문제 | 알고리즘 | 비고 |
|---|---|---|
| 소수 판정 (Primality) | Miller–Rabin 시험 | 오류 확률을 다중 시행으로 감소시킴 |
| 다항식 곱셈 | Schwartz‑Zippel 검증 | 다항식 동일성 검증에 사용 |
| 그래프 색칠 근사 | Randomized coloring algorithms | 기대값이 최적에 근접 |
연구 동향
- 탈난수화(Derandomization)
- 회로 복잡도와 난수 생성기의 구조적 가정에 기반한 연구가 활발히 진행 중이며, 특히 임계 회로와 일방향 함수의 존재 여부가 BPP = P와 직접 연관된다.
- 복합 확률적 클래스
- BPP와 다른 클래스(예: RP, ZPP, MA) 사이의 정확한 포함 관계는 아직 완전히 해결되지 않았다.
- 실제 컴퓨팅
- 암호학, 통계적 추정, 머신러닝 등에서 BPP 수준의 알고리즘이 실용적으로 활용된다.
참고 문헌
- Sipser, M. Introduction to the Theory of Computation, 3rd ed., 2012.
- Arora, S., Barak, B. Computational Complexity: A Modern Approach, 2009.
- Goldreich, O. Computational Complexity: A Conceptual Perspective, 2008.
요약
BPP는 확률적 알고리즘이 다항 시간 내에 제한된 오류율로 문제를 해결할 수 있는 복잡도 클래스로, 결정론적 클래스 P와 확률적 클래스 사이의 중요한 연결고리 역할을 한다. 현재 이론 컴퓨터 과학에서는 BPP의 탈난수화 가능성, 다른 복잡도 클래스와의 관계, 그리고 실용적 적용에 대한 연구가 활발히 진행되고 있다.
