co-RP

co-RP는 확률적 알고리즘을 사용하는 계산 복잡도 이론의 중요한 복잡도 종류 중 하나이다. 이 종류는 확률적 튜링 기계가 다항 시간 내에 풀 수 있는 문제들로 구성되며, 알고리즘의 답변에 대한 신뢰도가 비대칭적인 특징을 가진다. 구체적으로, 알고리즘이 '아니오'라고 답한 경우 그 결과는 항상 정확하다. 반면, 알고리즘이 '예'라고 답한 경우에는 실제 정답이 '예'일 수도, '아니오'일 수도 있어 일정 확률로 오답을 허용한다.

이러한 정의는 쌍대 관계에 있는 복잡도 종류인 RP의 개념을 뒤집은 것이다. RP는 알고리즘이 '예'라고 답하면 항상 정확한 반면, '아니오'라고 답할 때는 오류 가능성이 있다. 따라서 co-RP는 RP 문제의 '예'와 '아니오'를 바꾼, 즉 보수(complement)에 해당하는 문제들의 집합으로 이해할 수 있으며, 이 때문에 co-R이라고 표기하기도 한다.

co-RP는 다른 주요 복잡도 종류들과의 포함 관계를 가진다. 모든 결정론적 다항 시간 문제의 집합인 P는 co-RP의 부분집합이다. 또한, co-RP는 NP의 쌍대인 co-NP의 부분집합이다. co-RP와 RP의 교집합은 ZPP라는 또 다른 복잡도 종류를 이룬다. 한편, '예'와 '아니오' 답변 모두에서 오류 가능성을 허용하는 BPP는 co-RP를 포함한다.

이러한 알고리즘적 특성 덕분에 co-RP에 속하는 문제들은 '아니오' 인스턴스를 매우 신뢰할 수 있게 걸러낼 수 있다. 이는 소수 판별과 같은 수론 문제나 다항식 항등식 검증 등에서 유용하게 적용될 수 있는 계산 모델을 제공한다.

co-RP는 확률적 다항 시간 알고리즘을 사용하여 판정할 수 있는 문제들의 복잡도 종류이다. 이 클래스에 속하는 문제는 확률적 튜링 기계를 이용하여 다항 시간 내에 판정할 수 있으며, 그 알고리즘의 특성은 RP와 상호 보완적이다.

구체적으로, 어떤 문제가 co-RP에 속한다는 것은 다음 조건을 만족하는 확률적 알고리즘이 존재함을 의미한다. 알고리즘의 실행 결과가 '아니오'를 출력했다면, 이는 실제 정답이 항상 '아니오'임을 보장한다. 반면, 알고리즘의 실행 결과가 '예'를 출력했다면, 실제 정답은 '예'일 수도 있고 '아니오'일 수도 있다. 즉, '아니오' 답변에 대해서는 절대 오류가 없지만, '예' 답변에는 일정 확률로 오류가 허용된다.

이 정의는 RP의 정의와 정확히 대칭된다. RP 클래스는 '예' 답변이 항상 정확하지만 '아니오' 답변에는 오류가 있을 수 있는 반면, co-RP는 그 반대의 성질을 가진다. 이러한 관계 때문에 co-RP는 때로 co-R이라고도 표기된다. co-RP, RP, 그리고 두 클래스의 교집합인 ZPP, 합집합을 포함하는 더 넓은 클래스인 BPP 사이에는 명확한 포함 관계가 성립한다.

RP와 co-RP는 서로 상보적인 관계에 있는 확률적 복잡도 종류이다. RP는 확률적 알고리즘이 '예'라는 답을 낼 때 그 답이 항상 옳은 반면, '아니오'라는 답은 일정 확률로 틀릴 수 있는 문제들의 집합이다. 반대로 co-RP는 그 반대의 성질을 가진다. 즉, co-RP에 속하는 문제는 확률적 알고리즘이 '아니오'라는 답을 낼 때는 그 답이 항상 옳고, '예'라는 답은 일정 확률로 틀릴 수 있다.

이 두 복잡도 종류는 답변의 신뢰성이 반대 방향으로 보장된다는 점에서 대칭적이다. 어떤 문제가 RP에 속한다면, 그 문제의 '보수(complement)' 문제는 co-RP에 속하게 된다. 예를 들어, 어떤 그래프가 완전 그래프가 '아닌지'를 판단하는 문제가 RP라면, 그 그래프가 완전 그래프 '인지'를 판단하는 문제는 co-RP에 속하게 되는 식이다.

이러한 대칭성 때문에 RP = co-RP인지 여부는 중요한 미해결 문제 중 하나이다. 만약 두 복잡도 종류가 같다면, 이들의 교집합인 ZPP는 RP 및 co-RP와 동일해지게 된다. 그러나 현재까지는 RP와 co-RP가 서로 다른 복잡도 종류일 것으로 추측되고 있다.

co-RP에 속하는 문제를 해결하는 확률적 알고리즘은 '아니오'라는 답을 출력할 때는 그 정확성이 보장된다. 즉, 알고리즘이 어떤 입력에 대해 '아니오'를 답했다면, 그 문제의 실제 정답도 반드시 '아니오'이다. 이는 알고리즘이 오직 실제 정답이 '예'인 경우에만 '예'라고 답할 수 있음을 의미하며, 이때의 정답은 확률적이다. 반대로, 알고리즘이 '예'라고 답을 출력한 경우, 이는 실제 정답이 '예'일 가능성이 높음을 시사하지만, 일정 확률로 틀릴 수도 있다. 이러한 특성은 결정론적 알고리즘과는 구별되는 co-RP 알고리즘의 핵심적 성질이다.

이러한 알고리즘적 특성은 실용적으로 유용한 보장을 제공한다. 예를 들어, 어떤 문제에 대해 co-RP 알고리즘을 반복적으로 실행하여 한 번이라도 '아니오'라는 결과가 나온다면, 우리는 확실히 그 문제의 답이 '아니오'임을 알 수 있다. 이는 오류가 한쪽 방향으로만 발생할 수 있기 때문이다. 반면, 모든 실행에서 '예'라는 결과만 계속 나온다면, 실제 답이 '예'일 확신의 정도를 높일 수 있다. 이러한 단방향 오류(one-sided error) 모델은 검증이나 무작위 샘플링이 유용한 다양한 계산 문제에서 응용될 수 있다.

co-RP 알고리즘의 존재는 해당 문제가 난이도 측면에서 P에 가깝지만, 아직 결정론적 다항 시간 알고리즘이 발견되지 않았을 수 있음을 시사한다. P가 co-RP의 부분집합이므로, 모든 P 문제는 당연히 co-RP에 속한다. 그러나 그 역, 즉 모든 co-RP 문제가 P인지는 P-NP 문제와 마찬가지로 아직 해결되지 않은 열린 문제이다. 만약 RP와 co-RP가 동일하다면, 이들의 교집합인 ZPP와도 일치하게 되어, 확률적 알고리즘이 제공하는 양방향의 확률적 보장이 더욱 강력해지는 결과를 낳는다.

co-RP에 속하는 대표적인 문제로는 소수 판별 문제가 있다. 이 문제는 주어진 정수가 소수인지 아닌지를 판별하는 것으로, 확률적 알고리즘을 통해 효율적으로 해결할 수 있다. 예를 들어, 솔로베이-슈트라센 소수판별법은 주어진 수가 합성수일 경우 항상 '아니오'라는 정확한 답을 내놓지만, 소수일 경우에는 높은 확률로 '예'라는 답을 내놓는다. 이는 co-RP 알고리즘의 전형적인 특성으로, '아니오' 답변은 항상 신뢰할 수 있지만 '예' 답변은 일정 확률로 오류가 있을 수 있음을 보여준다.

또 다른 예시로는 다항식 동치성 문제가 있다. 이 문제는 두 개의 다항식이 동일한 함수를 나타내는지 판별하는 것이다. 확률적 알고리즘은 두 다항식이 다를 경우 항상 '아니오'를 정확히 보고하지만, 같을 경우에는 확률적으로 '예'를 보고한다. 이 외에도 행렬 곱 검증과 같은 특정 검증 문제들도 co-RP에 속할 수 있다.

이러한 문제들은 결정론적 알고리즘으로는 효율적으로 풀기 어려울 수 있지만, co-RP 알고리즘을 사용하면 다항 시간 내에 높은 신뢰도로 해결할 수 있다. co-RP의 이러한 성질은 계산 복잡도 이론에서 확률적 알고리즘의 유용성과 P-NP 문제를 이해하는 데 중요한 통찰을 제공한다.

co-RP는 확률적 알고리즘의 한 종류로, 결정론적 알고리즘과는 다른 특성을 보여준다. 이 복잡도 종류의 핵심은 '아니오'라는 답에 대한 절대적인 신뢰성에 있다. 알고리즘이 '아니오'를 출력했다면, 그 문제의 실제 답은 반드시 '아니오'라는 것이 보장된다. 반면, 알고리즘이 '예'를 출력한 경우에는 실제 답이 '예'일 수도 있고 '아니오'일 수도 있어, 일종의 '거짓 긍정'이 허용된다. 이러한 비대칭적 오류 허용은 RP와 정확히 반대의 성질을 가지며, 이 때문에 'co-'라는 접두사가 붙는다.

co-RP에 속하는 문제들은 다항식 시간 내에 해결 가능한 확률적 알고리즘이 존재하며, 그 알고리즘은 항상 올바른 '아니오' 답을 내놓는다. 이는 검증 과정에서 유용하게 활용될 수 있다. 예를 들어, 어떤 대상이 특정 조건을 '만족하지 않는다'는 것을 매우 높은 확률로, 그리고 빠르게 증명해낼 수 있다는 의미이다. 이러한 특성은 수학, 암호학, 알고리즘 이론 등 다양한 분야에서 이론적 중요성을 가진다.

co-RP와 RP의 교집합은 ZPP로 정의된다. ZPP는 항상 정답을 내놓지만, 평균 실행 시간이 다항 시간인 라스베이거스 알고리즘의 복잡도 종류이다. 즉, co-RP와 RP가 모두 가능한 문제들은 오류가 전혀 없는 확률적 알고리즘으로 해결할 수 있음을 의미한다. 또한, P가 co-RP의 부분집합이며, co-RP는 co-NP의 부분집합이라는 관계는 P-NP 문제와 깊이 연관되어 있다.

이 복잡도 종류는 때로 co-R이라고도 불리지만, 이 표기는 덜 일반적이다. co-RP에 대한 연구는 계산 복잡도 이론의 근본적인 질문들, 예를 들어 확률적 계산 능력이 결정론적 계산 능력을 얼마나 확장시키는지 이해하는 데 기여한다.

• ko.wikipedia.org