RP(복잡성)
RP (complexity)계산 복잡성 이론에서 무작위화된 다항 시간(RP)은 확률론적 튜링 기계가 존재하는 문제의 복잡성 등급이다.
| RP 알고리즘(1회 실행) | ||
|---|---|---|
답변 생성됨 맞아요. 대답하다 | 네 | 아니요. |
| 네 | ≥ 1/2 | ≤ 1/2 |
| 아니요. | 0 | 1 |
| RP 알고리즘(n runs) | ||
답변 생성됨 맞아요. 대답하다 | 네 | 아니요. |
| 네 | ≥ 1 − 2−n | ≤ 2−n |
| 아니요. | 0 | 1 |
| co-RP 알고리즘(1회 실행) | ||
답변 생성됨 맞아요. 대답하다 | 네 | 아니요. |
| 네 | 1 | 0 |
| 아니요. | ≤ 1/2 | ≥ 1/2 |
- 입력 크기에서 항상 다항식으로 실행됨
- 정답이 "아니오"인 경우 항상 "아니오"를 반환한다.
- 정답이 YES인 경우 최소 1/2 확률로 YES를 반환한다(그렇지 않으면 NO를 반환함).
즉, 알고리즘이 실행되는 동안 진짜 무작위 코인을 플립할 수 있도록 허용된다. 알고리즘이 YES를 반환할 수 있는 유일한 경우는 실제 답이 YES인 경우뿐이므로 알고리즘이 YES를 종료하고 YES를 생성하면 정답은 YES가 확실하지만, 알고리즘은 실제 답변과 무관하게 NO로 종료할 수 있다. 즉 알고리즘이 NO를 반환하면 틀릴 수 있다.
비록 이 이름이 재귀 언어의 클래스에 더 흔하게 사용되지만, 일부 저자들은 이 클래스를 R이라고 부른다.
만약 정답은 YES와 알고리즘 n번은 통계적으로 다른 사람들의 독립적 운영한다면, 그것은 확률 최소 1− 2−n은 그렇다가 적어도 한번 가지고 돌아 올것이다 그 결과에 운영된다.만약는 알고리즘을 100번 운영된다 그럼의 기회 때마다 확률이 우주선의 손상된보다 더 낮은 것 틀린 답을 준다. 알고리즘을 실행하는 컴퓨터의 [1]메모리 이런 의미에서 무작위 숫자의 출처를 이용할 수 있다면 RP의 대부분의 알고리즘은 매우 실용적이다.
정의에서 분율 1/2은 임의적이다. 설정된 RP는 1/2이 1보다 작은 임의의 일정한 0이 아닌 확률로 대체되더라도 정확히 동일한 문제를 포함할 것이다. 여기서 상수 평균은 알고리즘에 대한 입력과 무관하다.
형식 정의
언어 L은 다음과 같은 확률론적 튜링 기계 M이 존재하는 경우에만 RP에 있다.
- 모든 입력에서 다항식 시간에 대한 M 런
- 모든 x의 L에 대해, M은 1/2보다 크거나 같은 확률로 1을 출력한다.
- L이 아닌 모든 x에 대해, M 출력 0
또는 RP는 결정론적 튜링 기계만을 사용하여 정의할 수 있다. 언어 L은 다음과 같은 다항 p와 결정론적 튜링 기계 M이 존재하는 경우에만 RP에 있다.
- 모든 입력에서 다항식 시간에 대한 M 런
- L의 모든 x에 대해 M( , )= M(를) 만족하는 길이 p( x )의 문자열 y의 비율이 1/2보다 크거나 같다.
- L에 없는 모든 x와 p( x ), , y)= 의 모든 문자열 y에 대해
이 정의에서 문자열 y는 확률론적 튜링 기계가 만들었을 랜덤 코인 플립의 출력에 해당한다. 일부 애플리케이션의 경우 확률론적 튜링 기계를 언급하지 않으므로 이 정의가 바람직하다.
관련 복잡도 클래스
RP의 정의는 YES-instance가 NO-answer를 반환할 수 있기 때문에 YES-answer는 항상 옳고 NO-answer는 틀릴 수 있다고 말한다. 복잡도 등급 co-RP는 칭찬인데, 여기서 YES 답변은 틀릴 수 있고 NO 답변은 항상 옳다.
클래스 BPP는 YES와 NO 인스턴스 모두에서 오답을 줄 수 있는 알고리즘을 설명하므로 RP와 co-RP를 모두 포함한다. 세트 RP와 co-RP의 교차점을 ZPP라고 한다. RP를 R이라고 부를 수 있듯, 일부 저자들은 co-RP보다는 co-R이라는 이름을 사용한다.
P 및 NP 연결
P는 RP의 서브셋으로 NP의 서브셋이다. 마찬가지로 P는 co-NP의 서브셋인 co-RP의 서브셋이다. 이 포함이 엄격한지는 알려지지 않았다. 그러나 일반적으로 믿어지는 추측 P = BPP가 사실이라면 RP, co-RP, P 붕괴(모두 동일하다). P ≠ NP를 추가로 가정하면, 이는 RP가 NP에 엄격히 포함되어 있음을 의미한다. RP = co-RP인지 또는 RP가 NP와 co-NP의 교차점의 부분 집합인지 여부는 알 수 없지만 이는 P = BPP에 의해 암시된다.
현재 P에 있는 것으로 알려져 있지 않은 공동 RP의 문제의 자연스러운 예는 다항식 Identity Testing인데, 정수 위에 주어진 다변량 산술 식이 영항식인지 여부를 결정하는 문제다. 예를 들어, x·x - y·y - (x + y)·(x - y)는 0-polynormal이고, x·x + y는 0-polynomial이다.
때때로 사용하기 쉬운 RP의 대체 특성화는 입력 크기와 무관하게 적어도 계산 경로의 일정 부분 이상이 수용될 경우에만 기계가 수용하는 비결정론적 튜링 기계가 인식할 수 있는 문제의 집합이다. 반면에 NP는 하나의 수용 경로만 필요로 하는데, 이는 그 경로의 기하급수적으로 작은 부분을 차지할 수 있다. 이러한 특성화는 RP가 NP의 하위 집합이라는 사실을 명백하게 만든다.
참고 항목
참조
- ^ 이 비교는 의 252페이지의 Michael O. Rabin에 기인한다. Gasarch, William (2014), "Classifying Problems into Complexity Classes", in Memon, Atif (ed.), Advances in Computers, Vol. 95 (PDF), Academic Press, pp. 239–292.
 |
