1-3
BPP
BPP (bounded-error probabilistic polynomial time)
동전을 던져 가며 다항 시간에, 높은 확률로 옳게 풀 수 있는 문제의 모임
무작위 선택을 쓰는 다항 시간 알고리즘이 모든 입력에서 2/3 이상의 확률로 옳은 답을 내는 결정 문제의 모임이다. 되풀이해 다수결을 하면 틀릴 확률을 얼마든지 줄일 수 있어, 실용적으로는 「효율적으로 풀 수 있음」의 또 다른 기준이다. P ⊆ BPP 이고, 많은 연구자가 P = BPP 라고 믿는다. 충분히 어려운 함수가 존재하면 무작위를 없앨 수 있다는 결과들이 그 근거다. BPP 와 NP 사이의 포함 관계는 알려져 있지 않다.