인터랙티브 프루프 시스템

계산 복잡성 이론에서 쌍방향 증명 시스템은 두 당사자 사이의 메시지 교환으로서 계산을 모델화하는 추상적인 기계, 즉 프로베라와 검증 시스템이다.당사자들은 주어진 문자열이 언어에 속하는지 여부를 확인하기 위해 메시지를 교환함으로써 상호 작용한다.프로베서는 무한한 계산 자원을 가지고 있지만 신뢰할 수 없는 반면 검증자는 계산 능력을 경계하지만 항상 정직하다고 가정한다.검증자가 문제에 대한 답을 가지고 있고 그것이 옳다고 스스로 "확증"할 때까지 검증자와 검증자 사이에 메시지가 전송된다.

모든 대화형 증명 시스템에는 다음 두 가지 요구사항이 있다.

• 완전성: 만약 그 진술이 사실이라면, 정직한 검증자(즉, 프로토콜을 제대로 따르는 검증자)는 신뢰할 수 없는 프로바이더에 의해 이 사실을 확신할 수 있다.
• 건전성: 만약 그 진술이 거짓이라면, 어떤 프로베라도, 그것이 규약을 따르지 않더라도, 정직한 검증자에게 그것이 사실이라는 것을 납득시킬 수 있는 것은, 약간의 작은 가능성을 제외하고는 말이다.

시스템의 특수성, 그리고 따라서 시스템이 인식할 수 있는 언어의 복잡성 등급은 검증자에게 어떤 종류의 한계를 부여하는지, 그리고 그것이 어떤 능력을 부여받는지에 달려 있다. 예를 들어, 대부분의 인터랙티브 증명 시스템은 검증자의 무작위 선택을 하는 능력에 비판적으로 의존한다.그것은 또한 교환되는 메시지의 성격, 즉 그들이 얼마나 많은 것을 포함할 수 있는지에 따라 달라진다.쌍방향 증명 시스템은 하나의 기계만을 사용하여 정의된 전통적인 복잡성 등급에 대해 몇 가지 중요한 영향을 미치는 것으로 밝혀졌다.쌍방향 증명 시스템을 설명하는 주요 복잡도 클래스는 AM과 IP이다.

NP

복잡도 등급 NP는 매우 간단한 증명 시스템으로 간주될 수 있다.이 시스템에서 검증기는 결정론적 다항식 시간 기계(P 기계)이다.프로토콜은 다음과 같다.

• 프로베러는 입력을 보고 무제한 전력으로 솔루션을 계산하고 다항식 크기 증명서를 반납한다.
• 검증자는 인증서가 결정론적 다항식 시간에 유효한지 검증한다.만약 그것이 유효하다면, 그것은 받아들이고, 그렇지 않으면 거절한다.

유효한 증명서가 존재하는 경우, 프로베러는 항상 증명서를 줌으로써 검증자에게 승인하도록 할 수 있다.그러나 유효한 증명서가 없는 경우에는 입력 내용이 언어에 없고, 아무리 악의적이더라도 어떤 증명서가 거부되기 때문에 검증자를 달리 설득할 수 없다.

아서-머린-머린-아더 프로토콜

NP는 상호작용을 이용하는 것으로 볼 수 있지만, 1985년이 되어서야 상호작용을 통한 계산의 개념이 두 개의 독립된 연구자들에 의해 (복잡성 이론의 맥락에서) 구상되었다."임의성을 위한 트레이딩 그룹 이론"^[1]을 출판한 라슬로 바바이에 의한 한 가지 접근방식은 아서-머린(AM) 계급 계층 구조를 정의했다.이 발표에서 아서(검증자)는 확률론적 다항식 타임머신이고, 멀린(프로베베라)은 무한한 자원을 가지고 있다.

특히 등급 MA는 검증자가 결정론적인 것이 아니라 확률론적인 위 NP 상호작용의 단순 일반화다.또한 검증자가 항상 유효한 인증서를 수락하고 유효하지 않은 인증서를 거부하도록 요구하는 대신 다음과 같이 보다 관대하다.

• 완전성: 문자열이 언어에 있는 경우 프로베러는 검증자가 최소한 2/3의 확률로 수락할 수 있는 인증서를 부여할 수 있어야 한다(검증자의 무작위 선택에 따라 다름).
• 건전성: 문자열이 언어에 없는 경우, 아무리 악의적이더라도 검증자가 확률 1/3을 초과하는 문자열을 받아들이도록 설득할 수 없을 것이다.

이 기계는 잠재적으로 일반 NP 상호작용 프로토콜보다 더 강력하며, BPP 알고리즘은 실제 연산(BPP 참조)을 추상화하는 것으로 간주되기 때문에 인증서는 검증에 있어 실용적이다.

퍼블릭 코인 프로토콜 대 프라이빗 코인 프로토콜

공개 코인 프로토콜에서는 검증자가 임의로 선택한 내용이 공개된다.그들은 개인 코인 규약에서 비밀로 유지되고 있다.

바바이가 MA에 대한 자신의 증명 시스템을 정의한 같은 회의에서 샤피 골드워서, 실비오 미칼리, 찰스 라코프는^[2] 쌍방향 증명 시스템 IP[f(n)]를 정의하는 논문을 발표했다.이것은 크기 n의 입력에 대해 f(n) 라운드가 허용된 것을 제외하고 MA 프로토콜과 동일한 기계를 가지고 있다.각 라운드에서 검증자는 연산을 수행하고 프로베라에게 메시지를 전달하며 프로베러는 연산을 수행하고 다시 검증자에게 정보를 전달한다.마지막에는 검증자가 결정을 내려야 한다.예를 들어 IP[3] 프로토콜에서 시퀀스는 VPVPV로, 여기서 V는 검증자 턴이고 P는 프로베라 턴이다.

아서-머린 프로토콜에서, 바바이는 f(n) 라운드를 허용하는 유사한 클래스 AM[f(n)]을 정의했지만, 그는 기계에 한 가지 추가 조건을 붙였다: 검증기는 계산에 사용하는 모든 무작위 비트를 반드시 표시해야 한다.그 결과 검증자는 검증자가 어떤 임의 비트를 사용했는지 알면 검증자가 하는 모든 것을 시뮬레이션할 수 있을 만큼 강력하기 때문에 검증자는 프로베라의 어떤 것도 "숨길 수 없다"는 것이다.임의 비트("코인 플립")가 두 기계 모두 눈에 띄기 때문에 이것을 퍼블릭 코인 프로토콜이라고 한다.IP 접근방식은 대조적으로 프라이빗 코인 프로토콜이라고 불린다.

공공 동전의 본질적인 문제는 만약 검증자가 검증자가 언어에 없는 끈을 받아들이도록 악의적으로 설득하기를 원한다면, 검증자가 그것의 내부 상태를 숨길 수 있다면 계획을 무산시킬 수 있을 것처럼 보인다는 것이다.이것은 IP 증명 시스템을 정의하는 주된 동기였다.

1986년, 골드워서와 시퍼는^[3] 아마도 놀랍게도 프로베라에게서 동전이 날아가는 것을 숨기는 검증자의 능력은 결국 별로 도움이 되지 않는다는 것을 보여주었는데, 단 두 라운드만 더 있는 아서-머린 공개 코인 프로토콜은 모든 동일한 언어를 인식할 수 있다.결과적으로 퍼블릭 코인과 프라이빗 코인 프로토콜은 대략 동등하다.사실 1988년 바바이가 보여주듯이 AM[k]=모든 상수 k에 대한 AM이므로 IP[k]는 AM에 비해 이점이 없다.^[4]

이러한 등급의 힘을 입증하려면 그래프 이형성 문제, 즉 한 그래프의 정점을 다른 그래프와 동일하게 허용하는 것이 가능한지 여부를 결정하는 문제를 고려하십시오.증명서는 그래프를 동일하게 만드는 순열이기 때문에 이 문제는 NP에 있다.NP에 있는 것으로 알려져 있지 않은 공동 NP 문제인 그래프 이형성 문제의 보완은 AM 알고리즘을 가지고 있으며 이를 가장 잘 볼 수 있는 방법은 프라이빗 코인 알고리즘을 통해서인 것으로 나타났다.^[5]

IP

개인 동전은 도움이 되지 않을 수도 있지만, 더 많은 교류가 도움이 된다.확률론적 검증 기계와 만능 프로베러가 다항식 회진 수에 대해 상호 작용하도록 허용하면 IP라고 하는 문제의 등급을 얻게 된다.1992년 아디 샤미르(Adi Shamir)는 복잡성 이론의 중심 결과 중 하나에서 IP는 다항식 공간의 일반적인 결정론적 튜링 기계로 해결할 수 있는 문제의 등급인 PSPACE와 동일하다고 밝혔다.^[6]

QIP

시스템의 요소들이 양자 연산을 사용할 수 있도록 허용하면 시스템을 양자 쌍방향 증명 시스템이라고 하고, 그에 상응하는 복잡도 등급은 QIP라고 한다.^[7]일련의 결과는 QIP = PSPACE라는 2010년 돌파구로 절정에 달했다.^[8][9]

지식 제로

쌍방향 증명 시스템은 NP에 있다고 믿어지지 않는 문제를 해결할 수 있을 뿐만 아니라, 단방향 기능의 존재에 대한 가정 하에서 프로베러는 해결책에 대한 검증 정보를 전혀 주지 않고 해결책의 검증자를 납득시킬 수 있다.이는 검증자가 완전한 솔루션으로 신뢰할 수 없는 경우에 중요하다.처음에 검증자가 증명서를 보지 못했을 때 해결책이 있다고 확신할 수 있는 것은 불가능해 보이지만, 0지식 증명이라고 알려진 그러한 증명들은 사실 NP의 모든 문제에 대해 존재한다고 믿으며 암호화에 가치가 있다.0지식 증명서는 골드워서, 미칼리, 라코프에 의한 IP에 관한 최초의 1985년 논문에서 처음 언급되었지만, 그 힘의 범위는 오드 골드레이히, 실비오 미칼리, 에이비 위그더슨에 의해 나타났다.^[5]

MIP

IP 설계자들의 한 가지 목표는 가능한 가장 강력한 쌍방향 증명 시스템을 만드는 것이었는데, 처음에는 검증기를 더 강력하고 너무 비실용적으로 만들지 않고는 더 강력하게 만들 수 없을 것 같다.골드웨서 외1988년 "멀티베어 인터랙티브 증명:두 개의 독립적 프로버가 있는 MIP라고 하는 IP의 변형을 정의하는 난해성 가정을 제거하는 방법"이다.^[10]두 지지자는 일단 검증자가 그들에게 메시지를 보내기 시작하면 의사소통을 할 수 없다.범죄자와 그의 파트너가 별도의 방에서 심문받으면 거짓말을 하는지를 알기가 더 쉬우듯이, 만약 범죄자가 이중으로 확인할 수 있는 또 다른 프로베러가 있다면, 검증자가 언어에 없는 끈을 받아들이도록 속이려 하는 악의적인 프로베러를 발견하는 것은 상당히 쉽다.

사실 이것은 바바이, 포트나우, 룬드가 모든 문제의 클래스인 MIP = NEXPTIME, 즉 기하급수적인 시간에 비계수적인 기계로 해결할 수 있는 매우 큰 클래스라는 것을 보여줄 수 있을 정도로 큰 도움이 된다.^[11]NEXPTIME은 PSPACE를 포함하고 있으며, PSPACE를 엄격히 포함하고 있는 것으로 생각된다.2개 이상의 추가 프로버를 일정하게 추가해도 더 이상의 언어를 인식할 수 없다.이 결과는 이 정리의 "스케일다운" 버전으로 간주할 수 있는 유명한 PCP 정리의 길을 닦았다.

MIP는 또한 IP가 반드시 만들어야 하는 단방향 함수의 가정 없이 NP의 모든 언어에 대한 제로 지식 증명들을 기술할 수 있는 유용한 속성을 가지고 있다.이것은 분명히 깨질 수 없는 암호 알고리즘의 설계와 관계가 있다.^[10]더욱이 MIP 프로토콜은 일정한 회진수에서만 IP의 모든 언어를 인식할 수 있으며, 세 번째 프로베러가 추가되면 일정한 회진수에서 NEXPTIME의 모든 언어를 인식할 수 있어 IP에 대한 힘을 다시 보여 준다.

어떤 상수 k에 대해서도 k 프로버와 다항식적으로 많은 라운드를 갖는 MIP 시스템을 프로버 2개만 있는 등가 시스템으로 바꿀 수 있고, 라운드 수는 일정하다고 알려져 있다.^[12]

PCP

IP의 설계자들은 바바이의 쌍방향 증명 시스템의 일반화를 고려했지만, 다른 설계자들은 제한을 고려했다.매우 유용한 인터랙티브 증명 시스템은 PCP(f(n), g(n)로, 아서가 f(n) 랜덤 비트만 사용할 수 있고 멀린이 보낸 증명서의 g(n) 비트만 검사할 수 있는 MA의 제한이다(본질적으로 무작위 액세스를 사용한다).

다양한 PCP 수업에 대해 알기 쉬운 결과들이 많이 있다.${\displaystyle {\mathsf {PCP}}(0,{\mathsf {poly}})}$, the class of polynomial-time machines with no randomness but access to a certificate, is just NP. ${\displaystyle {\mathsf {PCP}}({\mathsf {poly}},0)}$, the class of polynomial-time machines with access to polynomially many random 비트는 co-RP이다.Arora and Safra's first major result was that PCP(log, log) = NP; put another way, if the verifier in the NP protocol is constrained to choose only ${\displaystyle O(\log n)}$ bits of the proof certificate to look at, this won't make any difference as long as it has ${\displaystyle O(\log n)}$ random bits to사용하다^[13]

게다가, PCP 정리는 증명 접근의 수가 상수까지 내려올 수 있다고 주장한다.즉, $N{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{P}}$= P ${\displaystyle \mathsf{C}}$ P${\displaystyle }$( ${\displaystyle l\mathsf{}}$ ${\displaystyle o}$ g${\displaystyle ,}$ ${\displaystyle \mathrm{O}}$( 1${\displaystyle }$)${\displaystyle {\mathsf{NP}}={\mathsf {PCP}}}({\mathsf {log},O($1$)\})\}$^[14]그들은 P = NP가 아닌 한 특정 NP 완성 문제의 최적화 버전에 대해 근사 알고리즘이 존재하지 않음을 증명하기 위해 NP의 이 귀중한 특성화를 사용했다. 그러한 문제들은 현재 근사치의 경도라고 알려진 분야에서 연구되고 있다.

참고 항목

• 오라클 머신

참조

교과서

• 2009년 3월, 케임브리지 대학 출판부의 아로라, 산제프, 바라크, 보아즈, "복잡성 이론: 현대적 접근법"
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. 10.4: 대화형 증명 시스템, 페이지 354–366.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. 제19.2절: 자연과 상호작용 프로토콜에 대한 게임, 페이지 469–480.

외부 링크

• 덱스터 코젠.대화형 교정쇄.CS682 Spring 2004 강의 노트코넬 대학의 컴퓨터 과학 학부.
• 복잡성 동물원:
  • 마, 마, 매엑스프, 매
  • AM, AMEXP, AM 교차 co-AM, AM[폴리로그], coAM, BP•NP
  • QMA, QMA+, QMA(2), QMA_log, QMAM
  • IP, MIP, IPP, QIP, QIP(2), compIP, frIP
  • PCP(r(n),q(n)
• 래리 고닉"프루프 포지티브?"대화형 교정 시스템에 대한 만화.