BPP (복잡도)
유계오차 확률적 다항시간(有界誤差 確率的 多項時間), BPP(Bounded-error, Probabilistic, Polynomial time)는 계산 복잡도 이론에서 확률적 튜링 기계로 모든 문제에 대해서 최대 1/3의 오류가 발생하면서 다항시간에 풀 수 있는 판정 문제의 집합이다.
어떤 문제가 BPP에 속하면, 내부적으로 동전을 던져서 무작위로 진행방향을 결정하여 이 문제를 풀 수 있는 알고리즘이 존재하고 이 알고리즘은 다항시간안에 실행된다. 이 알고리즘을 실행할 때, 잘못된 실행결과를 내놓을 확률은 최대 1/3이다. 여기서 잘못된 실행결과는 '예'나 '아니오'라는 대답을 내놓는 모든 경우에 해당한다.
여기서 1/3이라는 확률이 특수한 의미를 가지는 것은 아니다. 1/3 대신 입력값에 따라 달라지지 않는 0과 1/2 사이의 적당한 확률을 지정해서 정의해도 BPP의 집합은 변하지 않는다.
다른 복잡도 종류와 연관성[편집]
BPP는 여집합 연산에 대해서 닫혀있다. 즉, BPP=co-BPP이다. BPP가 NP의 부분집합인지 여부는 아직까지 알려지지 않았다. NP가 BPP의 부분집합인지도 아직 알려지지 않았다. 만약 NP가 BPP의 부분집합이면 NP=RP이고 PH ⊆ BPP이다.[1] (실제로 이것이 성립할 경우에는 NP-완전 문제에 대한 효율적인 해가 존재하므로, 많은 이들은 이것이 성립하지는 않을 것으로 추정한다.). RP와 co-RP는 BPP의 부분집합이고, BPP는 PP의 부분집합이라는 것이 알려졌으나 이 관계가 진부분집합인지는 알려진 바가 없다. BPP는 PH의 부분집합이다.
성질[편집]
주어진 숫자가 소수인지 아닌지 판명하는 것은 오랫동안 BPP에 속하지만 P에는 속하지 않는 문제라고 많은 사람들이 생각해왔다. 그러나 최근에는 소수 판별도 P라는 것이 밝혀졌다. 2002년에 마닌드라 아그라왈과 그의 학생 니라즈 카얄, 니틴 삭세나 등이 결정론적으로 소수인지 판별하는 알고리즘을 개발한 것이다.
BPP는 자기 자신에 비해 낮다. 즉, BPP 문제를 즉시 해결할 수 있는 BPP 기계 (BPP 신탁기계)는 이런 별도의 능력이 없는 기계보다 강력하지 않기 때문이다.
BPP는 난수를 사용하는 일반적인 튜링 기계에 해당한다. BQP는 BPP와 비슷하지만 튜링 기계가 아닌 양자컴퓨터에 해당한다.
어떤 언어가 BPP에 속하는지는 다항식 크기를 가진 불 회로로 판정할 수 있다. 자세한 내용은 회로 복잡도를 참고하라.
외부 링크[편집]
- (영어) Princeton CS 597E: Derandomization paper list
- (영어) 유사난수에 관한 하버드 강의자료 - 로그인 필요