확률적 알고리즘: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 로봇이 더함: fr:Algorithme probabiliste; 예쁘게 바꿈 |
잔글 Robot: Automated text replacement (- 수 밖에 + 수밖에) |
||
18번째 줄:
* '아니오'에 해당하는 입력은 100% 확실한 확률로 '아니오'라는 결과가 나온다.
* '예'에 해당하는 입력은 최소 50%의 확률로 '예'라는 결과가 나온다.
이것과 반대되는 종류는 [[RP (복잡도)|co-RP]]라고 한다. '예'와 '아니오' 두가지 답변 모두 오류가 발생할 수 있는 복잡도는 [[BPP]]라고 한다. 평균적으로 다항시간안에 올바른 답을 낼 수 있는 문제들의 종류는 [[ZPP]]이다. ('평균적'이기 때문에 어떤 입력의 경우에는 알고리즘이 무한히 돌아가면서 결과가 안 나올 수도 있다.) 이와 같은 여러 가지 복잡도 종류에 포함되지 않는다고 생각되는 문제는 [[NP-난해]]같은 문제들이며, 이런 문제들은 실제로 앞에서 언급한 복잡도 종류에 포함되지 않는다고 추정된다. 이런 문제들을 풀려면 확률적 알고리즘으로도 충분하지 않으며, [[근사 알고리즘]]을 사용할
역사적으로 볼 때, 확률적 알고리즘에 대한 연구가 시작된 것은 1976년에 제안된 [[밀러-라빈 소수판별법]] 이후이다. 그때까지는 주어진 수가 소수인지 아닌지 판별하는 [[결정론적 알고리즘]]은 존재하지 않았다.
| |||