PCP (복잡도)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
PCP(Probabilistically Checkable Proofs, 확률적 검사 가능 증명)는 복잡도 이론의 개념으로, 증명 검증 과정을 확률적으로 수행하는 방식을 정의한다. PCP 시스템은 증명자와 검증자로 구성되며, 검증자는 증명을 확인하기 위해 증명자에게 질의를 던진다. PCP는 NP(Non-deterministic Polynomial time, 비결정적 다항 시간)를 강화한 것으로 볼 수 있으며, 무작위성 복잡도와 질의 복잡도를 사용하여 복잡도 종류를 분류하는 데 사용된다. PCP 정리는 NP = PCP(log, O(1))이며, 근사 알고리즘의 어려움을 증명하는 데 유용하다. PCP는 계산 복잡도 이론, 특히 근사 어려움과 암호학에 적용된다.
더 읽어볼만한 페이지
- 확률적 알고리즘 - 알고리즘 정보 이론
알고리즘 정보 이론은 콜모고로프 복잡성을 기반으로 객체의 정보량을 측정하는 척도를 제공하며, 최소 설명 길이 원리 등에 응용될 수 있다. - 확률적 알고리즘 - 몬테카를로 알고리즘
몬테카를로 알고리즘은 정확한 답을 보장하지 않는 확률적 알고리즘으로, 단측 또는 양측 오류를 가지며 반복 실행으로 오류를 줄일 수 있고, 라스베가스 알고리즘과 함께 랜덤 알고리즘의 주요 분류를 이루며 다양한 분야에 응용된다. - 복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다. - 복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
| PCP (복잡도) |
|---|
2. 정의
'''PCP'''(Probabilistically Checkable Proof, 확률적 검사 가능 증명)는 대화형 증명 체계의 일종이다. 증명자(prover영어)는 메모리가 없는 오라클 머신이고, 검증자(verifier영어)는 다항 시간 확률적 알고리즘을 사용한다. 어떤 언어에 속하는 입력(즉, 답이 '예'인 경우)에 대해서는 검증자가 확실하게 받아들이는 증명(오라클)이 존재한다. 답이 '아니오'인 경우에는 어떤 증명이 주어지더라도 검증자가 적어도 1/2 확률로 거부한다. (이는 co-RP 복잡도 종류와 유사하다.)
'''PCP'''는 NP를 강화한 것으로 볼 수 있다. '''NP''' 문제에서는 증명을 검증하는 시간이 적어도 증명 자체의 길이만큼 걸릴 수 있지만, '''PCP''' 문제에서는 증명이 '''NP''' 문제의 증명보다 훨씬 길 수 있다.
'''PCP'''는 검증자가 사용하는 난수 개수와 오라클 질의 횟수에 따라 복잡도 종류를 분류한다. 검증자가 난수를 많이 사용할수록 증명을 더 다양하게 확인할 수 있다.
'''PCP'''(''r''(·), ''q''(·))는 입력 크기가 ''n''일 때, 검증자가 ''r''(''n'')번의 난수 생성과 ''q''(''n'')번의 오라클 질의를 통해 확률적으로 검사 가능한 증명을 갖는 언어들의 집합이다.
2. 1. 완전성과 건전성
결정 문제 ''L''이 주어졌을 때, 완전성 ''c''(''n'')과 건전성 ''s''(''n'')을 가진 ''L''에 대한 '''확률적으로 검사 가능한 증명 시스템'''은 다음과 같은 속성을 갖는다.- '''완전성''': 모든 ''x'' ∈ ''L''에 대해, 시스템의 증명자가 생성한 증명 ''π''가 주어지면, 검증자는 최소 확률 ''c''(''n'')로 진술을 수락한다.
- '''건전성''': 모든 ''x'' ∉ ''L''에 대해, 모든 증명 ''π''에 대해 검증자는 최대 확률 ''s''(''n'')로 진술을 실수로 수락한다.
2. 2. 복잡도 분류
PCP는 무작위성 복잡도(''r''(''n''))와 질의 복잡도(''q''(''n''))라는 두 함수를 사용하여 복잡도 종류를 분류한다. PCP(''r''(''n''), ''q''(''n''))는 검증자가 ''r''(''n'')번의 난수 생성과 ''q''(''n'')번의 신탁 질의를 수행하는 PCP 시스템의 복잡도 종류를 나타낸다.결정 문제 ''L''(또는 알파벳 집합 Σ를 가진 언어 L)이 주어졌을 때, 완전성 ''c''(''n'')과 건전성 ''s''(''n'')을 가진 ''L''에 대한 '''확률적으로 검사 가능한 증명 시스템'''은 증명자와 검증자로 구성된다. 길이가 n인 주장된 해답 x가 주어지는데, 이는 거짓일 수 있으며, 증명자는 ''x''가 L을 푼다고 명시하는 증명 ''π''를 생성한다 (증명은 문자열이다). 검증자는 무작위 오라클 튜링 머신 ''V''(검증자)이며, 이는 ''x''가 L을 푼다는 진술에 대해 증명 ''π''를 검사하고 진술을 수락할지 여부를 결정한다. 이 시스템은 다음과 같은 속성을 갖는다.
- '''완전성''': 모든 에 대해, 시스템의 증명자가 생성한 증명 ''π''가 주어지면, 검증자는 최소 확률 ''c''(''n'')로 진술을 수락한다.
- '''건전성''': 모든 에 대해, 모든 증명 ''π''에 대해 검증자는 최대 확률 ''s''(''n'')로 진술을 실수로 수락한다.
검증자의 계산 복잡도에 대해, 우리는 모든 길이 ''n''인 ''x''에 대해 ''V''가 사용하는 무작위 비트의 최대 수를 측정하는 ''무작위 복잡도'' ''r''(''n'')과 검증자가 모든 길이 ''n''인 ''x''에 대해 π에 대해 만드는 쿼리의 최대 수인 검증자의 ''쿼리 복잡도'' ''q''(''n'')을 갖는다.
위의 정의에서 증명의 길이는 일반적으로 알파벳 집합과 모든 증인을 포함하기 때문에 언급되지 않는다. 증명자에 대해 우리는 그가 문제의 해답에 어떻게 도달하는지 신경 쓰지 않고, 언어에서 해답의 멤버십에 대한 그가 제공하는 증명에 대해서만 신경 쓴다.
검증자가 이전 쿼리에 대한 답변을 받기 전에 모든 쿼리를 수행하면 "비적응적"이라고 한다.
복잡도 클래스 는 완전성 ''c''(''n'')과 건전성 ''s''(''n'')을 가지며, 검증자가 비적응적이고, 다항 시간 내에 실행되며, 무작위 복잡도 ''r''(''n'')과 쿼리 복잡도 ''q''(''n'')을 갖는 이진 알파벳에 대한 모든 결정 문제의 클래스이다.
축약 표기 는 때때로 에 사용된다. 복잡도 클래스 '''PCP'''는 로 정의된다.
3. 역사와 의의
PCP 이론은 확률적 검사 가능 증명 시스템의 성능을 연구하며, 계산 복잡성 이론(특히 근사 어려움) 및 암호학에 적용된다.
확률적으로 검증 가능한 증명의 정의는 1992년 아로라(Arora)와 사프라(Safra)에 의해 명시적으로 도입되었지만, 그 속성은 이전에 연구되었다. 1990년 바바이(Babai), 포트노우(Fortnow) 및 룬드(Lund)는 '''PCP'''[poly(''n''), poly(''n'')] = '''NEXP'''임을 증명하여 표준 증명('''NEXP''')과 확률적으로 검증 가능한 증명 사이의 첫 번째 비자명한 동등성을 제공했다. 1992년에 증명된 PCP 정리는 PCP영어(''O''(log ''n''), ''O''(1)) = NP영어임을 명시한다.
근사 어려움 이론은 확률적으로 검증 가능한 증명에서 완전성, 건전성, 알파벳 크기 및 쿼리 복잡성의 역할에 대한 자세한 이해를 요구한다. PCP 정리에 따르면, '''NP''' = '''PCP'''(''O''(log n), O(1))이며, 이는 근사 알고리즘을 위한 계산 복잡성을 증명하는데 도움이 된다.
간단하고 특별한 예는 다음과 같다. ('poly'는 다항식 양, 'log'는 대수적 양을 의미한다)
주목할 만한 사실은 다음과 같다.
4. 다른 복잡도 종류와의 관계
5. 예시
3-CNF-SAT을 푸는 PCP 알고리즘은 PCP 작동 방식의 간단한 예시이다. 3-CNF-SAT는 충족 가능성 문제 중 논리곱 정규형에서 각 절에 리터럴이 세 개씩 있는 경우를 말한다.
변수 ''m''개와 절 ''n''개로 된 식 ''F''가 있다고 가정한다. 증명자는 변수 ''m''개 모두를 만족하는 값을 할당해야 한다. 이때 모든 변수를 살펴보는 대신, O(log ''n'') 비트를 사용하여 임의로 절을 선택한다. 선택된 절의 변수 값을 확인하기 위해 세 번의 신탁 질의를 한다. 알아낸 값을 통해 절이 만족되면, 검증자는 1/''n'' 확률로 할당이 만족되는 것을 확인할 수 있다.
이 알고리즘을 ''n''번 반복하면, O(''n'' log ''n'')개의 난수 비트와 3''n''번의 신탁 질의만으로 상수 오차 한계를 가지면서 문제를 해결할 수 있다. 이 결과는 모든 '''NP''' 문제가 '''PCP'''(''n'' log ''n'', ''n'')에 속한다는 것을 보여준다.
6. 선형 PCP
선형 PCP는 증명이 유한체 의 원소 벡터 이고, PCP 오라클이 증명에 대해 선형 연산만 수행할 수 있는 PCP이다. 즉, 검증자 질의 에 대한 오라클의 응답은 선형 함수 이다. 선형 PCP는 SNARK로 컴파일될 수 있는 증명 시스템에서 중요한 응용 분야를 가지고 있다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com