아서-멀린 의정서

이 기사는 검증을 위해 추가 인용이 필요합니다. 신뢰할 수 있는 출처에 인용을 추가하여 이 기사를 개선하는 데 도움을 주세요. 출처가 없는 재료는 문제가 발생하여 제거될 수 있습니다. 출처 찾기 : "Arthur–Merlin protocol" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2016년 7월) (본 템플릿 메시지 제거 방법 및 시기에 대해 알아보기)

계산 복잡도 이론에서 Babai(1985)가 도입한 Arthur-Merlin 프로토콜은 검증자의 동전 던지기가 공개되도록 제한되는 상호 작용 증명 시스템입니다(즉, 속담에도 알려져 있음). Goldwasser & Sipser(1986)는 임의의 길이의 상호작용적 증명을 가진 모든 (공식적) 언어가 공개 동전과의 상호작용적 증명도 가지고 있음을 증명했습니다.

아서(Arthur)와 멀린(Merlin)이라는 프로토콜에 참여한 두 명을 감안할 때, 아서는 난수 생성 장치를 갖춘 표준 컴퓨터(또는 검증자)인 반면 멀린은 사실상 무한한 계산력(일명 속담)을 가진 오라클이라는 것이 기본 가정입니다. 그러나 멀린이 반드시 정직하다고 할 수는 없기 때문에 아서는 멀린의 질문에 응답하여 멀린이 제공한 정보를 분석하고 문제 자체를 결정해야 합니다. 문제는 "예"라는 대답이 나올 때마다 멀린이 일련의 응답을 하면 이 프로토콜로 해결할 수 있는 것으로 간주됩니다. 이로 인해 아서가 최소한 수락하게 됩니다. 2 ⁄의 시간에 해당하는 시간이고, 만약 답이 "아니오"라고 대답할 때마다 아서는 1 ⁄ 이상의 시간에 해당하는 시간을 절대 받아들이지 않을 것입니다. 따라서 Arthur는 결정과 질의를 수행하는 데 다항식 시간이 할당된다고 가정할 때 확률론적 다항식 시간 검증자 역할을 합니다.

엄마.

그러한 프로토콜 중 가장 간단한 것은 멀린이 아서에게 메시지를 보낸 후 아서가 확률 다항식 시간 계산을 실행하여 수락 여부를 결정하는 1-메시지 프로토콜입니다. (이것은 NP의 검증자 기반 정의와 유사하며, 유일한 차이점은 Arthur가 여기서 임의성을 사용할 수 있다는 것입니다.) 이 프로토콜에서 멀린은 아서의 동전 던지기에 접근할 수 없습니다. 왜냐하면 그것은 단일 메시지 프로토콜이고 아서는 멀린의 메시지를 받은 후에만 동전을 던지기 때문입니다. 이 프로토콜은 MA라고 불립니다. 비공식적으로 언어 L은 MA에 있습니다. 만약 언어의 모든 문자열에 대해 멀린이 아서를 보내 이 사실을 높은 확률로 확신시킬 수 있는 다항식 크기의 증거가 있다면, 언어가 아닌 모든 문자열에 대해 아서를 높은 확률로 확신시킬 수 있는 증거는 없습니다.

형식적으로, 복잡도 클래스 MA는 아서에 의한 계산보다 멀린의 유일한 움직임이 선행하는 아서-멀린 프로토콜에 의해 다항식 시간 내에 결정될 수 있는 결정 문제의 집합입니다. 즉, 길이가 n = x인 모든 입력 문자열 x에 대해 다항식 시간 결정론적 튜링 기계 M과 다항식 p, q가 존재하면 언어 L은 MA에 있습니다.

• x가 L 안에 있으면${\displaystyle z^{}}$ ∈${\displaystyle {}^{}}${${\displaystyle {0,}_{}}$ 1 }${\displaystyle }$q (n) $Pry$ ∈ {0, 1 } p (n) (M (x, y, z ) = 1) ≥ 2 / 3, {\displaystyle \exists z\in \{0,1\}^{q(n)}\,\Pr \n$olimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3,}$
• x가 L에 없으면${\displaystyle z^{}}$ ∈${\displaystyle {}^{}}${${\displaystyle {0,}_{}}$ 1 }${\displaystyle \mathrm{q}}$ (n) $Pry$ ∈ {0, 1 } p (n) (M (x, y, z ) = 0) ≥ 2 / 3. {\displaystyle \forall z\in \{0,1\}^{q(n)}\,\Pr \n$olimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3.}$

두 번째 조건은 대체적으로 다음과 같이 쓸 수 있습니다.

• x가 L에 없으면${\displaystyle z^{}}$ ∈${\displaystyle {}^{}}${${\displaystyle 0{,}_{}}$ 1 }${\displaystyle \mathrm{q}}$ (n) $Pry$ ∈ {0, 1 } p (n) (M (x, y, z ) = 1) ≤ 1 / 3. {\displaystyle \forall z\in \{0,${\displaystyle 1_{}}$\}^{q(n)}\,\Pr \n$olimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/3.}$

이를 위의 비공식적인 정의와 비교하기 위해 z는 멀린(다항식으로 크기가 경계를 이루는)에서 알려진 증명이고 y는 역시 다항식으로 경계를 이루는 아서가 사용하는 랜덤 문자열입니다.

AM

복잡도 클래스 AM(또는 AM[2])은 두 개의 메시지를 가진 아서-멀린 프로토콜에 의해 다항식 시간 내에 결정될 수 있는 결정 문제의 집합입니다. 쿼리/응답 쌍은 하나뿐입니다. 아서는 임의의 동전을 던져 그의 모든 동전 던지기 결과를 멀린에게 보내고, 멀린은 증명이라고 알려진 것으로 대답하고, 아서는 증명을 결정론적으로 확인합니다. 이 프로토콜에서 아서는 오직 동전 던지기의 결과를 멀린에게 보낼 수 있으며, 마지막 단계에서 아서는 이전에 생성된 무작위 동전 뒤집기와 멀린의 메시지만을 사용하여 수락할지 거절할지 결정해야 합니다.

즉, 길이가 n = x인 모든 입력 문자열 x에 대해 다항식 시간 결정론적 튜링 기계 M과 다항식 p, q가 존재하면 언어 L은 AM에 있습니다.

• x가 L 안에 있으면 ${\displaystyle {\mathrm{Pry}}_{}}$ ∈${\displaystyle {{}^{}}_{}}${${\displaystyle {0^{}}_{}}$, 1 ${\displaystyle {{\}}^{}}_{}}$p${\displaystyle \mathrm{}}$(${\displaystyle n^{})}$(∃${\displaystyle {}^{}z}$ ∈ {${\displaystyle 0}$, 1 ${\displaystyle \}}$ q (n) M (${\displaystyle \mathrm{x},}$ ${\displaystyle \mathrm{y},}$ ${\displaystyle z}$) = $1$) ≥ 2 / 3, {\displaystyle \Pr \n$olimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\geq 2/3,}$
• x가 L에 없으면 ${\displaystyle {\mathrm{Pry}}_{}}$ ∈${\displaystyle {{}^{}}_{}}${${\displaystyle {0^{}}_{}}$, 1 ${\displaystyle {{\}}^{}}_{}}$p${\displaystyle \mathrm{}}$(${\displaystyle n^{})}$(∀${\displaystyle {}^{}z}$ ∈ {${\displaystyle 0}$, 1 ${\displaystyle \}}$ q (n) M (${\displaystyle \mathrm{x},}$ ${\displaystyle \mathrm{y},}$ ${\displaystyle z\mathrm{}}$)$$= $0$) ≥ 2 / 3. {\displaystyle \Pr \n$olimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.}$

여기서 두 번째 조건은 다음과 같이 다시 쓸 수 있습니다.

• x가 L에 없으면 ${\displaystyle {\mathrm{Pry}}_{}}$ ∈${\displaystyle {{}^{}}_{}}${${\displaystyle {0^{}}_{}}$, 1 ${\displaystyle {{\}}^{}}_{}}$p${\displaystyle \mathrm{}}$(${\displaystyle n^{})}$(∃${\displaystyle {}^{}z}$ ∈ {${\displaystyle 0}$, 1 ${\displaystyle \}}$ q (n) M (${\displaystyle \mathrm{x},}$ ${\displaystyle \mathrm{y},}$ ${\displaystyle z\mathrm{}}$)$$= 1) ≤ $1$/ 3. {\displaystyle \Pr \n$olimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.}$

위와 같이 z는 멀린(다항식으로 크기가 경계를 이루는)의 증명으로 주장되는 것이고 y는 역시 다항식으로 경계를 이루는 아서가 사용하는 임의의 문자열입니다.

복잡도 클래스 AM[k]는 k개의 질의와 응답으로 다항식 시간에 결정할 수 있는 문제들의 집합입니다. 위에서 정의한 AM은 AM[2]입니다. AM[3]은 멀린이 아서에게 보내는 메시지로 시작하여 아서가 멀린에게 보내는 메시지로 시작하고 마지막으로 멀린이 아서에게 보내는 메시지로 시작합니다. 마지막 메시지는 항상 멀린에서 아서에게 전달되어야 합니다. 왜냐하면 아서가 대답을 결정한 후 멀린에게 메시지를 보내는 것은 결코 도움이 되지 않기 때문입니다.

특성.

• 완벽한 완전성을 요구하도록 정의가 변경되면 MA와 AM 모두 변경되지 않으며, 이는 x가 언어에 있을 때 Arthur가 확률 1(2/3 대신)로 수락함을 의미합니다.^[1]
• 임의의 상수 k ≥ 2에 대하여, 클래스 AM[k]는 AM[2]와 같습니다. k가 입력 크기와 다항식적으로 관련될 수 있다면 클래스 AM[poly(n)]은 클래스 IP와 동일하며, 이는 PSPACE와 동일한 것으로 알려져 있고 클래스 AM[2]보다 강하다고 널리 알려져 있습니다.
• AM[3]에는 MA가 포함되어 있으므로, AM에는 MA가 포함되어 있습니다. Arthur는 Merlin의 인증서를 받은 후, 필요한 수의 코인을 뒤집어서 Merlin에게 전송하고 응답을 무시할 수 있습니다.
• AM과 MA가 다른지 여부는 열려 있습니다. 그럴듯한 회로 하한(P=BPP를 암시하는 것과 유사)에서는 둘 다 NP와 동일합니다.
• AM은 클래스 BP ⋅NP와 동일합니다. 여기서 BP는 경계 오류 확률 연산자를 나타냅니다. ${\displaystyle \mathsf{또한}}$ ∃ ⋅$$B $PP$ {\displaystyle \existed \cdot {\mathsf {BPP}}이(가) 있습니다.PP)는 MA의 하위 집합입니다. ${\displaystyle \mathsf{MA}}$가${\displaystyle }$∃ ⋅$$B $PP$ {\$displaystyle$ \$exists \cdot {\mathsf${BPP}}과(와) 동일한지 여부는 미결 문제입니다.
• 멀린이 아서의 무작위 결정의 결과를 예측할 수 없는 개인 코인 프로토콜로 변환하면 일반적인 경우에는 상호 작용의 라운드 수가 최대 2개 증가합니다. 따라서 AM의 프라이빗 코인 버전은 퍼블릭 코인 버전과 동일합니다.
• MA는 NP와 BPP를 모두 포함합니다. BPP의 경우 Arthur가 Merlin을 무시하고 직접 문제를 해결할 수 있기 때문에, NP의 경우 Merlin이 Arthur에게 인증서만 보내면 되는데, 이 인증서는 Arthur가 다항식 시간에 결정적으로 검증할 수 있습니다.
• MA와 AM은 모두 다항식 계층에 포함됩니다. 특히 MA는 σ와 π의 교차점에, AM은 π에 포함되어 있습니다. 더욱이 MA는 "대칭적 교대"를 표현하는 복잡도 클래스인 ^[3]서브클래스 S에^P
  ₂ 포함되어 있습니다. 이것은 십서-라우테만 정리의 일반화입니다.
• AM은 다항식 크기 조언으로 비결정론적 다항식 시간에 계산 가능한 결정 문제 클래스인 NP/poly에 포함되어 있습니다. 그 증명은 애들먼 정리의 변형입니다.
• MA는 PP에 포함되어 있으며, 이 결과는 Vereschagin 때문입니다.^[4]
• MA는 양자 버전인 QMA에 포함되어 있습니다.^[5]
• AM에는 두 그래프가 동형이 아닌지 판단하는 문제가 포함되어 있습니다. 프라이빗 코인을 이용한 프로토콜은 아래와 같으며 퍼블릭 코인 프로토콜로 변환이 가능합니다. 두 그래프 G와 H가 주어졌을 때, Arthur는 그들 중 하나를 임의로 선택하고, 그 정점들의 임의의 순열을 선택하고, 순열 그래프 I을 Merlin에게 제시합니다. 멀린은 내가 G에서 만들어졌는지 H에서 만들어졌는지 대답해야 합니다. 만약 그래프가 동형이 아니면 멀린은 (내가 G와 동형인지 확인함으로써) 완전히 확실하게 대답할 수 있을 것입니다. 그러나 그래프가 동형인 경우에는 G 또는 H를 사용하여 I를 만들 수 있으며, 마찬가지로 가능합니다. 이 경우 멀린은 그들을 구분할 방법이 없고 기껏해야 1/2의 확률로 아서를 설득할 수 있고, 이것은 반복에 의해 1/4로 증폭될 수 있습니다. 이것은 사실 제로 지식 증명입니다.
• AM에 coNP가 포함된 경우 PH = AM. 이는 그래프 동형이 다항식 계층 구조의 붕괴를 의미하기 때문에 NP-완전일 가능성이 낮다는 증거입니다.
• 임의의 문제에 대해 "정수$$ 계수와 최대 d의 차수를 갖는 다변량 다항식 ${\displaystyle {fi}_{}}$ ${\$ 집합이 주어졌을 때, 그들은 공통 복소수 0을 갖는가?"라는 문제가 AM에 있는 것으로 알려져 있습니다.^[6]

참고문헌

서지학

• Babai, László (1985), "Trading group theory for randomness", STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, pp. 421–429, ISBN 978-0-89791-151-1.
• Goldwasser, Shafi; Sipser, Michael (1986), "Private coins versus public coins in interactive proof systems", STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, ACM, pp. 59–68, ISBN 978-0-89791-193-1.
• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4.
• Madhu Sudan의 고급 복잡성에 대한 MIT 과정

외부 링크

• 복잡성 동물원: MA
• 콤플렉스 동물원: AM