확률적 알고리즘: 두 판 사이의 차이

내용 삭제됨 내용 추가됨
잔글편집 요약 없음
TedBot (토론 | 기여)
잔글 봇: 문단 이름 변경 (주석 → 각주)
15번째 줄:
* '아니오'에 해당하는 입력은 100% 확실한 확률로 '아니오'라는 결과가 나온다.
* '예'에 해당하는 입력은 최소 50%의 확률로 '예'라는 결과가 나온다.
이것과 반대되는 종류는 [[RP (복잡도)|co-RP]]라고 한다. '예'와 '아니오' 두가지 답변 모두 오류가 발생할 수 있는 복잡도는 [[BPP]]라고 한다. 평균적으로 다항시간안에 올바른 답을 낼 수 있는 문제들의 종류는 [[ZPP]]이다. ('평균적'이기 때문에 어떤 입력의 경우에는 알고리즘이 무한히 돌아가면서 결과가 안 나올 수도 있다.) 이와 같은 여러 가지 복잡도 종류에 포함되지 않는다고 생각되는 문제는 [[NP-난해]]같은 문제들이며, 이런 문제들은 실제로 앞에서 언급한 복잡도 종류에 포함되지 않는다고 추정된다. 이런 문제들을 풀려면 확률적 알고리즘으로도 충분하지 않으며, [[근사 알고리즘]]을 사용할 수밖에 없다.
 
역사적으로 볼 때, 확률적 알고리즘에 대한 연구가 시작된 것은 1976년에 제안된 [[밀러-라빈 소수판별법]] 이후이다. 그때까지는 주어진 수가 소수인지 아닌지 판별하는 [[결정론적 알고리즘]]은 존재하지 않았다.
 
밀러-라빈 소수판별법은 두 개의 자연수 ''k''와 ''n''사이의 '증거'(witness)라는 [[이항관계]]를 사용한다. '증거' 관계는 다음과 같은 성질을 가진다.
* ''n''에 대한 증거가 존재하면, ''n''은 [[소수 (수론)|합성수]]이다. (즉, ''n''은 [[소수 (수론)|소수]]가 아니다.),
* ''n''이 합성수이면 ''n''보다 작은 수 중에서 최소한 3/4은 ''n''이 합성수라는 증거이다.
* ''k''와 ''n''이 주어졌을 때, ''k''가 ''n''이 합성수라는 것에 대한 증거인지 아닌지 판별하는 빠른 알고리즘이 존재한다.
위와 같은 내용에서 소수 판별 문제가 Co-RP에 속하는 것을 알 수 있다.
 
합성수 ''n''보다 작은 임의의 수를 100번 선택하여 알고리즘을 실행시킨다면, 이런 '증거'를 못 찾을 확률은 (1/4)<sup>100</sup>이다. 그러므로 거의 대부분의 경우에서, 이와 같은 소수 판별법은 매우 좋은 알고리즘이라고 생각할 수 있다. 특히''n''이 아주 크다면, 이 방법 이외에는 효율적인 알고리즘이 없다. 알고리즘을 여러 번 시행하면 오류가 일어날 확률을 원하는 만큼 줄일 수도 있다.
 
작은 확률로 오류가 발생하더라도 알고리즘을 조금만 주의해서 실행시키면 오류가 일어날 확률을 천문학적으로 작은 숫자만큼 줄일수 있기 때문에, 실제로 오류가 발생하는 것은 그다지 큰 문제가 되지 않는다. 실제로 결정론적으로 소수를 판별하는 다항시간 알고리즘이 [[AKS 소수 판별법|발견]]되었어도, 다양한 암호 관련 소프트웨어에서는 기존의 소수 판별법을 그대로 사용하고 있으며, 소수 판별 분야에서는 결정론적 알고리즘이 가까운 시일 안에 기존 확률적 알고리즘을 대체할 수는 없을 것으로 보인다.
45번째 줄:
}
 
여기서 모서리 (u,v)를 줄인다는 것은 새로운 꼭짓점 w를 더하고 (u,x) 혹은 (v,x)를 (w,x)로 바꾸고, G에서 u와 v를 없애는 것이다.
 
<math>n</math>이 이 그래프의 꼭짓점의 개수라고 하면, 알고리즘은 최소 <math>n^{-2}\ </math>의 확률로 최소 절단을 찾아낸다. 그러므로 위 알고리즘을 <math>n^2 \log n\ </math>번 실행시켜서 실행 결과중 가장 작은 값을 선택하면, 높은 확률로 최소 절단을 찾아낼 수 있다.
55번째 줄:
* Christos Papadimitriou (1993) Computational Complexity, Addison Wesley, ISBN 0-201-53082-1, Chapter 11: Randomized computation, pp.241–278.
 
== 주석각주 ==
<references/>