PCP 정리

PCP theorem
포스트 서신 문제와 혼동해서는 안 된다.

계산 복잡성 이론에서, PCP 정리(PCP 특성화 정리라고도 함)는 NP 복잡성 등급의 모든 의사결정 문제가 일정한 질의 복잡성과 로그 무작위성 복잡성의 확률적으로 확인 가능한 증명(임의화된 알고리즘으로 확인할 수 있는 증명)을 가지고 있다고 기술하고 있다(로그리듬 숫자를 사용한다).임의의 비트의).

PCP 정리는 어떤 보편적인 상수 K에 대해, 모든 n에 대해, 길이 n의 문장에 대한 수학적인 증명은 그 증명의 K 글자만 검사하는 임의화된 알고리즘에 의해 공식적으로 99%의 정확도로 검증 가능한 다른 길이 증명 폴리(n)로 다시 쓰여질 수 있다고 말한다.

PCP 정리는 다양한 최적화 문제에 대한 효율적인 근사 알고리즘 설계에 내재된 난이도를 조사하는 근사치 계산 경도 이론의 초석이다."쿡의 정리 이후 가장 중요한 복잡성 이론의 결과"[1]로 인고 베게너가, "혁신적인 아이디어가 풍부한 인상적인 일련의 작품[…]의 정점"으로 오드리드 골드리치가 묘사하고 있다.[2]

형식명세서

PCP의 정리에는 다음과 같이 되어 있다.

NP = PCP[O(log n), O(1)].

PCP 및 근사치 경도

PCP 정리의 대안적 공식은 제약조건 만족도 문제의 만족 가능한 제약조건의 최대 부분은 어떤 일정한 요인 내에서 근사치하기 어려운 NP라고 명시한다.

형식적으로는 일부 상수 K와 α < 1에 대해 다음과 같은 약속 문제(Lyes, Lno)는 NP-하드 결정 문제다.

  • Lyes = {φ: φ의 모든 제약조건이 동시에 충족됨}
  • Lno = {φ: 모든 할당은 φ 제약의 α 부분보다 적은 부분을 만족한다.

여기서 φ은 부울 알파벳에 대한 제약조건 만족도 문제로서 제약조건당 K 변수가 가장 많다.

이 정리의 결과로, 최대 부울 공식 만족도, 그래프에 설정된 최대 독립성, 그리고 래치에 대한 최단 벡터 문제를 포함한 많은 자연 최적화 문제에 대한 해결책은 P = NP가 아닌 한 효율적으로 근사할 수 없음을 보여줄 수 있다.이러한 결과를 PCP 정리라고도 부르기도 하는데, 이는 일부 추가적인 구조를 가진 NP에 대해 확률적으로 확인할 수 있는 증거로 볼 수 있기 때문이다.

증명

약한 결과의 증거인 NP = PCP[n3, 1]는 덱스터 코젠의 강의 중 하나에서 주어진다.[3]

역사

PCP 정리는 상호작용이 가능한 증명과 확률적으로 확인할 수 있는 증명에 대한 긴 작업 라인의 정점이다.표준 증명서와 확률적으로 확인할 수 있는 증명과 관련된 첫 번째 정리는 NEXP ⊆ PCP[poly(n), poly(n), poly(n), babai, Fortnow & lund(1990))에 의해 증명된 진술이다.

"PCP 정리"라는 이름의 어원

PCPc(n), s(n)[r(n), q(n)]라는 표기법은 확률적으로 확인할 수 있는 증명에 설명되어 있다.표기법은 특정 복잡성 등급을 반환하는 함수의 표기법이다.위에 언급된 설명을 참조하십시오.

이 정리의 이름("PCP 정리")은 아마도 "확률적으로 확인할 수 있는 증명"을 의미하는 "PCP"에서 유래했거나, 위에서 언급된 표기법(또는 둘 다)에서 유래했을 것이다.

제1차 정리 이후의 역사 [1990년]

Subsequently, the methods used in this work were extended by Babai, Lance Fortnow, Levin, and Szegedy in 1991 (Babai et al. 1991), Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 (Arora & Safra 1992) to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1998 (Arora et al. 1998).

The 2001 Gödel Prize was awarded to Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy for work on the PCP theorem and its connection to hardness of approximation.

2005년에 Irit Dinur는 확장형 그래프를 사용하여 PCP 정리에 대한 상당히 단순한 증거를 발견했다.[4]그녀는 이 일로 2019 괴델 상을 받았다.[5]

PCP 정리의 양자 아날로그

2012년 토머스 비딕과 이토 츠요시는 '멀티플레이어 게임에 관여할 수 있는 얽힌 프로버들의 능력에 강한 한계를 보였다'는 결과를[6] 발표했다.도릿[6] 아하로노프 교수는 결과가 언론에 보도됐을 [7][8]때 "기본적으로 PCP 정리를 이끈 다중접적 증명서에 대한 이전 논문의 양자 아날로그"라고 평가했으므로 이는 PCP 정리의 양자 아날로그를 증명하는 단계가 될 수 있다.[8]

2018년 토마스 비딕과 아난드 나타라얀은 무작위 축소를 통해 양자 PCP 정리의 게임 변형을 입증했다[9].QMA ⊆ MIP*[log(n),1,1/2]을 명시하고 있는데, 여기서 MIP*[f(n),c,s]는 f(n)비트 클래식 통신을 가진 다중 프로버 양자 쌍방향 증명 시스템의 복잡도 등급이며, 완전성은 c, 건전성은 s이다.그들은 또한 해밀턴 버전의 양자 PCP 추측, 즉 일정한 약속 갭 c - s를 가진 지역 해밀턴식 문제는 QMA-hard이며 게임 양자 PCP 정리를 함축하고 있음을 보여주었다.

메모들

  1. ^ Ingo Wegener (2005). Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer. p. 161. ISBN 978-3-540-21045-0.
  2. ^ Oded Goldreich (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. p. 405. ISBN 978-0-521-88473-0.
  3. ^ Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. London: Springer-Verlag. pp. 119–127. ISBN 9781846282973.
  4. ^ 2005년 사전 인쇄 ECCC TR05-046을 참조하십시오.논문의 권위 있는 버전은 디누르(2007)이다.
  5. ^ EATSC 2019 괴델 상, 2019-09-11을 회수했다.
  6. ^ a b Ito, Tsuyoshi; Vidick, Thomas (2012). "A multi-prover interactive proof for NEXP sound against entangled provers". arXiv:1207.0550 [quant-ph].
  7. ^ Hardesty, Larry (2012-07-30). "MIT News Release: 10-year-old problem in theoretical computer science falls". MIT News Office. Archived from the original on 2014-02-02. Retrieved 2012-08-10. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they're just as important for the insight they provide into the complexity of computational problems.
  8. ^ a b Hardesty, Larry (2012-07-31). "10-year-old problem in theoretical computer science falls". MIT News Office. Archived from the original on 2012-08-01. Retrieved 2012-08-10. Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito’s paper is the quantum analogue of an earlier paper on multiprover interactive proofs that “basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years.” Similarly, she says, the new paper “could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory.”
  9. ^ Natarajan, A.; Vidick, T. (October 2018). "Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS): 731–742. arXiv:1801.03821. Bibcode:2018arXiv180103821N. doi:10.1109/FOCS.2018.00075. ISBN 978-1-5386-4230-6.

참조