맨위로가기

ZPP (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

ZPP(Zero-error Probabilistic Polynomial time)는 확률적 알고리즘을 사용하는 계산 복잡도 종류 중 하나로, RP(Randomized Polynomial time)와 co-RP의 교집합과 같다. ZPP는 라스베이거스 알고리즘으로 다항 시간 안에 풀 수 있는 문제들의 집합으로, 항상 정확한 답을 내놓지만 실행 시간은 확률적이다. ZPP는 RP와 co-RP의 교집합이므로, ZPP 알고리즘은 RP 알고리즘과 co-RP 알고리즘을 결합하여 구성할 수 있으며, 실행 시간의 기댓값은 다항 시간이 된다. ZPP는 보수 연산에 닫혀 있으며, 자기 자신에 대해 low이다. P는 ZPP에 포함되며, 많은 과학자들은 P = ZPP일 것으로 추측한다.

2. 정의

ZPP는 RP와 co-RP의 교집합으로 정의된다. 이는 ZPP를 라스베이거스 알고리즘으로 다항 시간 안에 풀 수 있는 문제들의 집합으로 정의하는 것과 같다.

2. 1. RP와 co-RP를 이용한 정의

'''ZPP'''는 '''RP'''와 '''co-RP'''의 교집합과 정확히 일치한다. 이는 '''ZPP'''의 정의로 사용되기도 한다.

어떤 문제 L에 대해, 다음과 같은 두 가지 알고리즘 A와 B가 존재한다고 가정한다.

  • A는 '''RP''' 알고리즘이다.
  • B는 '''co-RP''' 알고리즘이다. (A와 B는 서로 다른 알고리즘일 수 있다.)


ZPP 알고리즘은 다음과 같이 구성된다.

1. 입력이 주어지면, 먼저 A 알고리즘을 실행한다. 만약 '예'를 반환하면 답은 '예'이다.

2. A 알고리즘이 '예'를 반환하지 않으면, B 알고리즘을 실행한다. 만약 '아니오'를 반환하면 답은 '아니오'이다.

3. B 알고리즘도 '아니오'를 반환하지 않으면, A 알고리즘을 실행하는 단계로 돌아간다.

두 알고리즘 중 하나만 틀린 답을 낼 수 있으며, 한 번의 반복에서 틀린 답이 나올 확률은 50%이다. 따라서 k번째 반복까지 갈 확률은 k에 대해 지수적으로 줄어들며, 실행 시간의 기댓값은 다항 시간이 된다.

이러한 성질을 통해 '''RP'''와 '''co-RP'''의 교집합은 '''ZPP'''에 포함됨을 알 수 있다.

반대로, '''ZPP'''가 '''RP'''와 '''co-RP'''의 교집합에 포함됨을 보이기 위해, ZPP에 속하는 문제를 해결하는 라스베이거스 알고리즘 C가 있다고 가정한다. 그러면 다음과 같은 '''RP''' 알고리즘을 만들 수 있다.

  • C를 평균 실행 시간의 두 배 이상 실행한다. 만약 답이 나오면, 그 답을 출력한다. 답이 나오지 않으면 '아니오'를 출력한다.


마르코프 부등식에 따르면, 이 알고리즘이 멈출 때까지 C가 답을 찾지 못할 확률은 1/2 이하이다. 즉, 답이 '예'인 입력에 대해 실행을 멈추고 '아니오'라는 틀린 답을 낼 확률이 1/2 이하라는 의미이며, 이는 '''RP'''의 정의와 일치한다. C가 답을 내지 못했을 때 '예'를 출력하도록 알고리즘을 변경하면, ZPP가 '''co-RP'''에 속한다는 것도 같은 방식으로 증명할 수 있다.

2. 2. 라스베이거스 알고리즘을 이용한 정의

ZPP는 라스베이거스 알고리즘으로 다항 시간 안에 풀 수 있는 문제들의 집합으로 정의할 수 있다. 라스베이거스 알고리즘은 항상 정확한 답을 내놓는 확률적 알고리즘이다.

ZPP 알고리즘 C가 존재한다고 가정하면, 다음과 같은 RP 알고리즘을 구성할 수 있다.

  • C를 평균 실행 시간의 두 배 이상 실행한다.
  • 답이 나오면 그 답을 출력하고, 나오지 않으면 '아니오'를 출력한다.


마르코프 부등식에 의해 이 알고리즘이 정답을 출력할 확률은 1/2 이상이다. co-RP 알고리즘도 유사하게 구성할 수 있는데, C가 답을 내지 못했을 때 '예'를 출력하도록 바꾸면 된다.

3. 증거와 증명

NP, RP, ZPP는 집합의 구성원 자격을 증명하는 개념과 관련지어 생각할 수 있다.
정의: 집합 X에 대한 검증자 V는 다음과 같은 튜링 머신이다.


  • x가 X에 속하면, V(x, w)를 승인하는 문자열 w가 존재한다.
  • x가 X에 속하지 않으면, 모든 문자열 w에 대해 V(x, w)는 거부한다.


여기서 문자열 w는 구성원 증명으로 생각할 수 있다. 짧은 증명(입력 크기에 대한 다항식으로 제한되는 길이)의 경우, 효율적으로 검증할 수 있으며(V는 다항 시간 결정적 튜링 머신), 이 문자열 w를 '증거'라고 한다.
참고:

  • 이 정의는 매우 비대칭적이다. x가 X에 속한다는 증명은 단일 문자열이면 충분하지만, x가 X에 속하지 않는다는 증명은 모든 문자열의 집합이 필요하며, 그중 어떤 것도 구성원 증명이 아니다.
  • X에 있는 모든 x에 대해 X의 구성원에 대한 증거가 있어야 한다.
  • 증거는 전통적인 증명일 필요는 없다. V가 확률적 튜링 머신이고 x가 X에 포함된 경우 x를 승인한다면, 증거는 기계가 x를 승인하도록 이끄는 동전 던지기 문자열이 될 수 있다 (X의 모든 구성원이 증거를 가지고 있고 기계가 비구성원을 승인하지 않는 경우).
  • 관련된 개념은 비구성원 증명, 즉 여집합의 구성원 증명이다.


NP, RP, ZPP 클래스는 구성원 자격에 대한 증거를 가진 집합이며, 각 클래스에서 증거의 특성은 다음과 같다.

  • NP 클래스는 증거가 존재하기만 하면 된다. 매우 드물 수 있다. 다항식인 f를 사용하여 2f(|x|)개의 가능한 문자열 중에서, 검증자가 승인하는 것은 단 하나만 있으면 된다 (x가 X에 속하는 경우. x가 X에 속하지 않으면, 검증자가 승인하는 문자열은 없다).
  • RP 및 ZPP 클래스의 경우, 임의로 선택된 문자열이 증거가 될 가능성이 높다.


Co-RP는 x가 X에 속하지 않는 경우, 임의로 선택된 모든 문자열이 비구성원 증거가 될 가능성이 높은 집합의 클래스이다. ZPP는 임의의 문자열이 x가 X에 속하는지, 또는 x가 X에 속하지 않는지에 대한 증거가 될 가능성이 높은 집합의 클래스이다.

이 정의를 RP, Co-RP, ZPP의 다른 정의와 연결하는 것은 쉽다. 확률적 다항 시간 튜링 머신 V*w(x)는 V*의 임의의 테이프를 동전 던지기 시퀀스가 기록된 V의 두 번째 입력 테이프로 대체하여 결정적 다항 시간 튜링 머신 V(x, w)에 해당한다. 증거를 임의의 문자열로 선택함으로써, 검증자는 다음과 같은 확률적 다항 시간 튜링 머신이 된다.

  • RP의 경우: x가 X에 속할 때 x를 승인할 확률이 크고 (예를 들어 1/2보다 큼), x가 X에 속하지 않는 경우 0.
  • Co-RP의 경우: x가 X에 속하지 않을 때 x를 거부할 확률이 크지만 x가 X에 속하는 경우 0.
  • ZPP의 경우: X의 구성원으로서 x를 정확하게 승인하거나 거부할 확률이 크지만, x를 잘못 승인하거나 거부할 확률은 0.


가능한 증거를 반복적으로 임의로 선택하면, 임의의 문자열이 증거일 확률이 크기 때문에 입력을 승인하거나 거부하는 데 예상되는 다항 시간 알고리즘을 제공한다. 반대로, 튜링 머신이 (주어진 x에 대해) 예상 다항 시간인 경우, 실행의 상당 부분이 다항 시간으로 제한되어야 하며, 이러한 실행에 사용된 동전 시퀀스가 증거가 된다.

ZPP는 BPP와 대조해야 한다. BPP 클래스는 증거를 요구하지 않지만, 증거는 충분하다 (따라서 BPP는 RP, Co-RP, ZPP를 포함한다). BPP 언어는 x가 X에 속하는 경우, (분명하게) 다수의 문자열 w에 대해 V(x,w)가 승인하고, 반대로 x가 X에 속하지 않는 경우 (분명하게) 다수의 문자열 w에 대해 거부한다. 단일 문자열 w는 결정적일 필요가 없으므로 일반적으로 증명 또는 증거로 간주될 수 없다.

3. 1. 검증자 (Verifier)

집합 X에 대한 검증자 V는 다음과 같은 조건을 만족하는 튜링 기계이다.

  • 만약 ''x''가 ''X''에 속하면, ''V''(''x'',''w'')를 수락하는 문자열 ''w''가 존재한다.
  • 만약 ''x''가 ''X''에 속하지 않으면, 모든 문자열 ''w''에 대해 ''V''(''x'',''w'')는 거부한다.


여기서 문자열 ''w''는 ''x''가 ''X''에 속한다는 구성원 증명으로 생각할 수 있다. 만약 이 증명 ''w''가 짧다면 (입력 ''x''의 크기에 대한 다항식으로 표현되는 길이), ''V''는 다항 시간 결정적 튜링 기계이므로 효율적으로 검증할 수 있다. 이때 ''w''를 "증거"라고 부른다.
참고:

  • 이 정의는 비대칭적이다. ''x''가 ''X''에 속한다는 것을 증명하기 위해서는 단 하나의 문자열 ''w''만 있으면 되지만, ''x''가 ''X''에 속하지 않는다는 것을 증명하기 위해서는 ''V''(''x'',''w'')를 거부하는 모든 문자열 ''w''의 집합이 필요하다.
  • ''X''에 속하는 모든 ''x''에 대해 구성원 증명 ''w''가 존재해야 한다.
  • 증거 ''w''는 전통적인 의미의 증명일 필요는 없다. 만약 ''V''가 확률적 튜링 기계라면, ''w''는 ''V''가 ''x''를 수락하도록 하는 동전 던지기 결과의 문자열이 될 수 있다.
  • 비구성원 증명은 여집합의 구성원 증명이다.


NP, RP, ZPP 클래스는 구성원 자격에 대한 증거를 가진 집합이다. NP의 경우, 증거가 존재하기만 하면 된다. 반면, RP와 ZPP에서는 임의로 선택된 문자열이 증거가 될 가능성이 높다.

3. 2. NP, RP, ZPP의 증거

'''NP''', '''RP''', '''ZPP'''는 멤버십 증거를 기준으로 하는 복잡도 종류이다.

  • '''NP''': 어떤 집합 X에 대해, x가 X에 속한다는 것을 증명하는 증거 w가 *존재하기만 하면* 된다. 이 증거는 매우 드물 수 있다. 즉, 가능한 많은 문자열 중에서 단 하나의 문자열만이 검증자에 의해 수락될 수 있다. (x가 X에 속하는 경우. x가 X에 속하지 않으면 어떤 문자열도 수락되지 않는다.)
  • '''RP''': x가 X에 속할 때, 임의로 선택된 문자열 w가 증거가 될 확률이 높다(1/2 이상). x가 X에 속하지 않는 경우에는 어떤 문자열도 증거가 될 수 없다.
  • '''ZPP''': 임의의 문자열 w가 x가 X에 속하는지, 혹은 속하지 않는지에 대한 증거가 될 확률이 높다. 즉, w는 x가 X의 원소라는 증거일 수도 있고, X의 원소가 아니라는 증거일 수도 있다.


이 정의들은 '''RP''', co-'''RP''', '''ZPP'''의 다른 정의들과 쉽게 연결된다. 예를 들어, '''RP'''의 경우, 확률적 다항 시간 튜링 머신은 x가 X에 속하면 높은 확률로 수락하고, 그렇지 않으면 0의 확률로 수락한다. '''ZPP'''의 경우, 튜링 머신은 높은 확률로 x의 멤버십을 정확하게 판정하고, 잘못 판정할 확률은 0이다.

4. 다른 복잡도 종류와의 관계

ZPP는 RP와 co-RP 둘 다에 포함된다. 이는 ZPP = RP ∩ co-RP이기 때문이다.

P는 ZPP에 포함되며, 많은 과학자들은 P = ZPP일 것으로 추측한다. 즉, 모든 라스베이거스 알고리즘에는 동등한 결정론적 다항 시간 알고리즘이 존재한다는 것이다.

ZPP = EXPTIME인지 여부는 아직 밝혀지지 않았다. (같을 가능성은 거의 없어 보인다.) P ≠ EXPTIME이므로 P = ZPP임이 밝혀지면 ZPP ≠ EXPTIME임이 증명된다.

5. 복잡도 이론적 성질

ZPP는 보수 연산에 대해 닫혀 있다. 즉, ZPP = co-ZPP이다.

ZPP는 자기 자신에 대해 low이다. 다시 말해, ZPP 문제를 즉시 해결할 수 있는 ZPP 머신(ZPP 오라클 머신)은 이러한 추가적인 능력이 없는 머신보다 더 강력하지 않다. 이를 기호로 나타내면 '''ZPP''''''ZPP''' = '''ZPP'''이다.

'''ZPP''''''NP''''''BPP''' = '''ZPP''''''NP'''.

'''NP''''''BPP'''는 '''ZPP''''''NP'''에 포함된다.


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com