확률적으로 확인할 수 있는 증거

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2012년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

계산 복잡성 이론에서 확률적으로 확인할 수 있는 증명(PCP)은 한정된 양의 무작위성을 사용하여 무작위화된 알고리즘에 의해 확인될 수 있는 증명의 한 유형이며, 증명의 경계된 비트 수를 읽는다. 그런 다음 알고리즘은 정확한 증거를 수용하고 확률이 매우 높은 부정확한 증거를 기각해야 한다. 복잡도 등급 NP의 검증자 기반 정의에 사용된 표준 증명서(또는 증명서)도 확인 절차가 전체 증거를 결정적으로 읽고 항상 정확한 증거를 수용하며 부정확한 증거를 거부하기 때문에 이러한 요건을 충족한다. 그러나 이들을 흥미롭게 하는 것은 무작위성을 본질적으로 이용하여 몇 비트만 읽어도 확인할 수 있는 확률적으로 체크할 수 있는 증명의 존재다.

확률적으로 확인할 수 있는 증거는 필요한 질의 수와 사용된 무작위성의 양에 따라 많은 복잡성 등급을 야기한다. 클래스 PCP[r(n),q(n)]는 최대 r(n) 랜덤 비트를 사용하고 증명의 최대 q(n)비트를 사용하여 다항식 시간에 검증할 수 있는 확률적으로 확인할 수 있는 증거를 가지고 있는 의사결정 문제의 집합을 말한다.^[1] 달리 명시되지 않는 한, 정확한 증명은 항상 받아들여져야 하며, 부정확한 증명은 1/2 이상의 확률로 기각되어야 한다. 계산 복잡성 이론의 주요 결과인 PCP 정리는 PCP[O(log n),O(1)] = NP라고 기술하고 있다.

정의

의사결정 문제 L(또는 알파벳이 σ인 언어 L)을 고려할 때, 0 ≤ s(n) ≤ c(n) ≤ 1인 완전성 c(n) 및 건전성 s(n)에 대한 확률적으로 확인할 수 있는 증명 시스템은 프로베라와 검증자로 구성된다. 길이가 n인 주장 용액 x가 거짓일 수 있는 경우, 프로베러는 증명 π을 생성하여 x가 L을 해결한다는 것을 명시한다(x , L, 증거는 문자열^* ∈). 그리고 검증자는 임의의 오라클 튜링 머신 V(검증자)로, x가 L(또는 x ∈ L)을 해결한다는 진술에 대한 증명 π을 확인하고 그 진술의 수용 여부를 결정하는 것이다. 이 시스템에는 다음과 같은 속성이 있다.

• 완성도: 어떤 x ∈ L에 대해, 시스템의 프로베러가 작성한 증명 π에 따라, 검증자는 최소한 c(n)의 확률로 그 진술을 받아들인다.
• 건전성: 어떤 x ∉ L에 대해서도, 그리고 어떤 증거 π에 대해서도, 검증자는 잘못하여 대부분의 s(n)에서 확률로 그 진술을 받아들인다.

검증자의 계산 복잡성에 대해, 우리는 V가 모든 길이 n에 대해 사용하는 임의 비트의 최대 개수를 측정하기 위한 임의성 복잡성 r(n)을 가지고 있으며 검증자의 쿼리 복잡성 q(n)는 V가 전체 길이 n에 대해 π에 대해 수행하는 최대 쿼리 수입니다.

위의 정의에서 증명의 길이는 보통 알파벳 집합과 모든 증인을 포함하기 때문에 언급되지 않는다. 프로베라에게 있어서, 우리는 그것이 어떻게 문제의 해결책에 도달하는지에 대해 신경쓰지 않는다; 우리는 단지 그것이 해결책의 언어의 멤버쉽에 대해 주는 증거에 대해서만 신경쓴다.

검증자는 이전 질의에 대한 답을 받기 전에 모든 질의를 하면 적응하지 못한다고 한다.

복잡도 등급 PCP_{c(n), s(n)}[r(n), q(n)]는 완전성 c(n)와 건전성 s(n)의 이진 알파벳에 대해 확률적으로 확인할 수 있는 증명 시스템을 가진 모든 의사결정 문제의 등급으로, 검증자가 비적응성이며, 임의성 복잡성 r(n)과 질의 복잡성 q(n)가 있다.

속기 표기법 PCP[r(n), q(n)]는 때때로 PCP_{1, ½}[r(n), q(n)]에 사용된다. 복잡도 등급 PCP는 PCP_{1, ½}[O(log n), O(1)]로 정의된다.

역사와 의의

확률적으로 체크 가능한 증명 이론은 매개변수의 다양한 제한사항(완전성, 건전성, 무작위성 복잡성, 질의 복잡성, 알파벳 크기)에서 확률적으로 체크 가능한 증명 시스템의 힘을 연구한다. 그것은 계산 복잡성(특히 근사치의 경도)과 암호법에 응용된다.

확률적으로 확인할 수 있는 증거의 정의는 비록 그들의 성질은 일찍이 연구되었지만 1992년에 아로라와 사프라에 의해 명백하게 도입되었다.^[2] 1990년 Babai, Fortnow, Lund는 PCP[폴리(n), 폴리(n)] = NEXP라는 것을 증명하여 표준 교정쇄(NEXP)와 확률적으로 검사 가능한 교정쇄 사이의 최초의 비교 동등성을 제공하였다.^[3] 1992년에 입증된 PCP 정리에서는 PCP[O(log n),O(1)] = NP라고 되어 있다.^[2][4]

근사치 경도 이론은 확률적으로 확인할 수 있는 증명에서 완전성, 건전성, 알파벳 크기, 질의 복잡성의 역할을 상세하게 이해해야 한다.

특성.

계산 복잡성의 관점에서, 매개변수의 극단적 설정에 대해서는 확률적으로 확인 가능한 증명에 대한 정의가 표준 복잡도 등급과 동등한 것으로 쉽게 볼 수 있다. 예를 들어, PCP[r(n), q(n)]의 다른 설정에 대해 다음과 같은 사항이 있다.

• PCP[0, 0] = P (P는 무작위성이 없고 증거에 대한 접근성이 없는 것으로 정의된다.)
• PCP[O(log(n)), 0] = P(랜덤 비트의 로그 수는 다항 시간 내에 로그 길이의 모든 임의 문자열을 시도할 수 있으므로 다항 시간 튜링 기계에는 도움이 되지 않는다.)
• PCP[0,O(log(n))] = P (임의성이 없으면 그 증거는 고정 로그 크기의 문자열로 생각할 수 있다. 다항식 타임머신은 가능한 모든 로그 크기의 증거를 다항식 시간에 시도할 수 있다.)
• PCP[폴리(n), 0] = coRP (coRP의 정의에 따라)
• PCP[0, poly(n)] = NP(NP의 검증자 기반 정의에 의한)

PCP 정리 및 MIP = NEXP는 다음과 같이 특징 지을 수 있다.

• PCP[O(log n),O(1)] = NP(PCP 정리)
• PCP[poly(n),O(1)] = PCP[poly(n),poly(n)] = NEXP(MIP = NEXP)

PCP[r(n), q(n)] ⊆ NTIME(폴리(n,2q^O(r(n))(n)))도 알려져 있다. 특히 PCP[log n, poly(n)] = NP. 반면 NP ⊆ PCP[o(log n),o(log n)]이면 P = NP.^[2]

선형 PCP

선형 PCP는 ${\displaystyle {\mathbb{}}^{}}$oracle F n ${\$^{$n$의 요소 벡터로서, PCP 오라클이 증거 위에서만 선형 연산을 할 수 있는 PCP이다. 즉, 검증 질의 $q{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\$에 대한 오라클의 응답은 선형$$ $함수{\displaystyle }$ f${\displaystyle }$(${\displaystyle q}$ , ${\displaystyle \pi }$) ${\displaystyle f(q,\pi )}.$ 선형 PCPs는 SNARKs로 컴파일할 수 있는 증명 시스템에 중요한 응용 프로그램을 가지고 있다$.$

참고 항목

• 인터랙티브 프루프 시스템

참조

외부 링크

• 수학 백과사전 홀로그래피 증빙서
• Subhash Khot이 2008년 뉴욕 대학교에서 PCP 과정을 노트했다.
• 2005년 워싱턴 대학의 라이언 오도넬과 벤카테산 구루스와미가 PCP를 정리한 이력 및 PCP 과정 노트.
• 복잡성 동물원: PCP