P/폴리

계산 복잡성 이론에서 P/폴리(P/poly)는 다항 시간 튜링 기계에 의해 다항 경계 조언 기능이 인정된 언어의 복잡성 등급이다.또한 다항식 크기 회로 패밀리를 가진 언어의 클래스 PSIZE로 동등하게 정의된다.^[1]^[2]이것은 언어를 인식하는 기계가 입력의 길이에 따라 다른 조언 기능을 사용하거나 다른 회로를 사용할 수 있으며, 조언 기능이나 회로는 입력의 크기에 따라서만 달라질 수 있다는 것을 의미한다.

예를 들어, 인기 있는 밀러-라빈 소수성 테스트는 P/폴리 알고리즘으로 공식화될 수 있다: "advises"는 테스트할 후보 값의 목록이다.모든 복합 n비트 번호가 리스트에 증인을 포함시킬 것이 확실하도록 최대 n개의 값 목록을 사전 계산하는 것이 가능하다.예를 들어 32비트 숫자의 원시성을 올바르게 판단하려면 a = 2, 7 및 61을 테스트하는 것으로 충분하다.^[3]후보 증인의 짧은 리스트의 존재는 각 합성 n에 대해 가능한 모든 값의 3/4가 증인이라는 사실에서 비롯된다. 아래 P/poly의 BPP가 모든 입력 크기에 적합한 리스트가 존재한다는 증거에 있는 것과 유사한 간단한 계산 논거는 비록 그것이 비싸다고 생각할지 모르지만, 모든 입력 크기에 적합한 리스트가 존재한다는 것을 보여준다.

P/poly는 P나 BPP와 같은 다른 다항 시간 클래스와 달리 일반적으로 계산에 실용적인 클래스로 간주되지 않는다.사실, 그것은 모든 해석 불가능한 단언어를 포함하고 있는데, 그 중 어느 것도 실제 컴퓨터로 풀 수 있는 것은 없다.한편, 입력 길이가 상대적으로 적은 숫자로 경계가 되어 있고 조언 문자열이 짧다면, 위의 예와 같이 별도의 고가의 사전 처리 단계와 빠른 처리 단계로 실용 알고리즘을 모델링하는 데 사용할 수 있다.

형식 정의

복잡도 등급 P/poly는 다음과 같이 SIZE 단위로 정의할 수 있다.

{\mathsf{P/poly}=\c컵 _{c\in \mathb{N}}{{\mathsf {SIZE}}(n^{c})

여기서 ${\mathsf {SIZE}}(n^{c})$ ${\mathsf {SIZE}}(n^{c})$ ${\mathsf {SIZE}}(n^{c})$ ${\mathsf {SIZE}}(n^{c})$ ${\mathsf {SIZE}}(n^{c})$ ${\mathsf {SIZE}}(n^{c})$ ) ${\displaystyle {\mathsf {SIZE}(n^{c})$ 는 다항식 크기 회로 패밀리가 해결할 수 있는 의사결정 문제의 집합이다 ${\mathsf {SIZE}}(n^{c})$ .

또는 "자문을 받는" 튜링 머신을 사용하여 ${\mathsf {P/poly}}$ / ${\mathsf {P/poly}}$ ${\mathsf {P/poly}}$ l ${\$ 을(를) 정의할 수 있다 ${\mathsf {P/poly}}$ .이러한 기계는 각 $n$ 에 대해 $\alpha _{n}$ ${\$ 를 가지며 $\alpha _{n}$ 입력에 n $크기$ 가 있을 때마다 계산에 사용할 수 있다.

$T,a:\mathbb {N} \rightarrow \mathbb {N}$ , $T,a:\mathbb {N} \rightarrow \mathbb {N}$ = $T,a:\mathbb {N} \rightarrow \mathbb {N}$ → $T,a:\mathbb {N} \rightarrow \mathbb {N}$ ${\$ 를) 함수로 한다 $T,a:\mathbb {N} \rightarrow \mathbb {N}$ .The class of languages decidable by time-T(n) Turing machines with $a(n)$ advice, denoted ${\mathsf {DTIME}}(T(n))/a(n)$ , contains every language L such that there exists a sequence ${\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N$ $\alpha _{n}\in \{0,1\}^{a(n)}$ $\alpha _{n}\in \{0,1\}^{a(n)}$ $\alpha _{n}\in \{0,1\}^{a(n)}$ } $\alpha _{n}\in \{0,1\}^{a(n)}$ $\alpha _{n}\in \{0,1\}^{a(n)}$ $\alpha _{n}\in \{0,1\}^{a(n)}$ ${\$ 이 $\alpha _{n}\in \{0,1\}^{a(n)}$ (가) 있는 문자열과 TM M이 만족스러운 $\{\alpha _{n}\}_{n\in \mathbb {N} }$ 문자열 중 $\{\alpha _{n}\}_{n\in \mathbb {N} }$ }}}}}}}}}}}}}}}}}}}}}}}{{{{n(가 있음

M(x,\alpha _{n}=1\왼쪽 오른쪽 화살표 x\in L

$x\in \{0,1\}^{n}$ machine $x\in \{0,1\}^{n}$ , $x\in \{0,1\}^{n}$ $x\in \{0,1\}^{n}$ $x\in \{0,1\}^{n}$ {\ $displaystyle x\in \{0,1\}^{n$ 입력 시 $(x,\alpha _{n})$ , $(x,\alpha _{n})$ $(x,\alpha _{n})$ ${\displaystyle$ ( $O(T(n))$ $,\alpha _{n})$ 시스템 $(x,\alpha _{n})$ M은 $O(T(n))$ O $O(T(n))$ ( $O(T(n))$ T $O(T(n))$ ) ${\displaystystystyle$ O $(T)}$ 단계에서 실행된다 $O(T(n))$ .^[4]

P/폴리 중요도

P/poly는 몇 가지 이유로 중요한 수업이다.이론 컴퓨터 과학의 경우 P/폴리(Poly)에 의존하는 몇 가지 중요한 속성이 있다.

NP ⊆ P/poly가 2 $\Sigma _{2}^{\mathsf {P}}$ {\ $displaystyle \Sigma _{2}^{\mathsf{P}}}}$ 로 무너지면 PH(다항식 계층 구조). $\Sigma _{2}^{\mathsf {P}}$ 이 결과는 Karp-Lipton 정리이며, 나아가 NP / P/poly는 AM = MA를 내포하고 있다.
If PSPACE ⊆ P/poly then ${\mathsf {PSPACE}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ , even PSPACE = MA.

증거: PSpace의 L 언어를 생각해 보십시오.PSPACE 기계에 의해 프로베라의 동작이 수행될 수 있는 L을 위한 인터랙티브 증명 시스템이 존재하는 것으로 알려져 있다.가정으로 프로베러는 다항식 크기 회로로 대체될 수 있다.따라서 L에는 다음과 같은 MA 프로토콜이 있다.멀린은 회로를 증거로 보내고, 아서는 별도의 도움 없이도 IP 프로토콜을 직접 시뮬레이션할 수 있다.

P^#P ⊆ P/polly이면^#P P = MA이다.^[6]그 증거는 상기와 유사하며, 영구적 및 영구적 #P-완전성을 위한 쌍방향 프로토콜에 기초한다.
If EXPTIME ⊆ P/poly then ${\mathsf {EXPTIME}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ (Meyer's theorem), even EXPTIME = MA.
NEXPTIME ⊆ P/poly이면 NEXPTIME = EXPTIME, 심지어 NEXPTIME = MA. 반대로 NEXPTIME = MA는 NEXPTIME ⊆ P/poly를^[7] 내포하고 있다.
EXP가^NP P/poly일 경우 ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ N ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ = ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ ${\$ $NP}}}=\Sigma _{2}^{{2}^{P}\cap \Pi _{2}^{\mathsf{P}}}($ Buhrman, Homer)
MA의 지수 버전인 MA는_EXP P/폴리에는 포함되어 있지 않은 것으로 알려져 있다.

증명: MA_EXP ⊆ P/폴리인 경우 PSPACE = MA(위 참조)패딩으로 EXPSPACE = MA_EXP, 따라서 EXPSPACE ⊆ P/poly를 사용하지만 이는 대각선으로 거짓으로 증명될 수 있다.

P/poly가 중요한 가장 흥미로운 이유 중 하나는 NP가 P/poly의 하위 집합이 아니라면 P ≠ NP라는 속성이다.이 관찰은 P ≠ NP를 증명하려는 많은 시도의 중심이었다.랜덤 오라클 A의 경우 NP는^A 확률 1을 갖는 P^A/poly의 하위 집합이 아니라고 알려져 있다.^[1]

암호학 분야에서도 P/폴리(P/poly)가 사용된다.보안은 흔히 P/poly 적으로 정의된다.BPP와 같은 대부분의 실제 연산 모델을 포함하는 것 외에도, 이것은 또한 적들이 무지개 테이블의 구성에서처럼 일정 길이까지의 입력에 대해 무거운 사전 컴퓨팅을 할 수 있다는 가능성을 인정한다.

P/poly의 모든 언어가 희박한 언어는 아니지만, P/poly의 모든 언어에서 희박한 언어로 다항 시간 튜링(Turing)이 감소한다.^[9]

경계 오류 확률론적 다항식이 P/poly에 포함되어 있음

애들만의 정리를 보면 BPP ⊆ P/poly로 되어 있는데, 여기서 BPP는 다항 시간에 양면 오차가 있는 임의화된 알고리즘으로 해결할 수 있는 문제의 집합이다.더 약한 결과는 처음에 Leonard Adleman, 즉 RP ⊆ P/poly에 의해 증명되었고,^[10] 이 결과는 BPP ⊆ P/poly에 의해 Bennett와 Gill에 의해 일반화되었다.^[11]정리변형은 L/poly에 BPL이, NP/poly에 AM이 포함되어 있음을 보여준다.

증명

L을 BPP의 언어가 되게 하고, M(x,r)을 오류 ≤ 1/3로 L을 결정하는 다항 시간 알고리즘으로 한다(여기서 x는 입력 문자열이고 r은 랜덤 비트의 집합이다).

M 48n을 실행하고 결과의 과반수를 차지하는 새로운 기계 M'(x,R)을 구축한다(여기서 n은 입력 길이, R은 48n 독립적으로 무작위 rs의 시퀀스).따라서 M'은 또한 다항식 시간이며, Chernoff 바운드에 의한 오차 확률 1 1/e을ⁿ 가진다(BPP 참조).우리가 R을 고칠 수 있다면 결정론적인 알고리즘을 얻을 수 있을 것이다.

${\mbox{Bad}}(x)$ ( ${\mbox{Bad}}(x)$ ) ${\mbox{Bad}(x)$ 이 ${\mbox{Bad}}(x)$ (가) $\{R:M{'}(x,R){\text{ is incorrect}}\}$ { $\{R:M{'}(x,R){\text{ is incorrect}}\}$ : $\{R:M{'}(x,R){\text{ is incorrect}}\}$ ′ ( $\{R:M{'}(x,R){\text{ is incorrect}}\}$ , R $\{R:M{'}(x,R){\text{ is incorrect}}\}$ )이(가) $\{R:M{'}(x,R){\text{ is incorrect}}\}$ $}$ {\ $displaystyle$ \{ $R:$ $M{'}(x,R){\text{$ 이 $올바르지$ 않음 $\{R:M{'}(x,R){\text{ is incorrect}}\}$ 다음 정보를 참조하십시오.

\forall x\,{\mbox{Prob}_{R}[R\in {\mbox{Bad}(x)]\leq {\frac {1}{e^{n}}}}.

입력 크기는 n이므로 가능한 입력은 2개ⁿ 있다.따라서 조합 한계치에 의해 임의 R이 적어도 하나의 입력 x에 대해 불량일 확률은 다음과 같다.

{\mbox{Prob}_{R}[\exists x\,R\in {\mbox{Bad}}}\leq {2^{n}{e^{n}}}}<1}

즉, R이 일부 x에 나쁜 확률은 1보다 작으므로 모든 x에 좋은 R이 있어야 한다.이러한 R을 P/폴리 알고리즘의 조언 문자열로 사용하십시오.

참조

^ ^a ^b Lutz, Jack H.; Schmidt, William J. (1993), "Circuit size relative to pseudorandom oracles", Theoretical Computer Science, 107 (1): 95–119, doi:10.1016/0304-3975(93)90256-S, MR 1201167
^ "Lecture notes on computational complexity by Peter Bro Miltersen" (PDF). Archived from the original (PDF) on 2012-02-23. Retrieved 2009-12-25.
^ 소수점 찾기 & 소수점 증명
^ Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
^ Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer (1995), "If NP has polynomial-size circuits, then MA = AM", Theoretical Computer Science, 137 (2): 279–282, doi:10.1016/0304-3975(95)91133-B, MR 1311226
^ Babai, László; Fortnow, Lance; Lund, Carsten (1991), "Nondeterministic exponential time has two-prover interactive protocols", Computational Complexity, 1 (1): 3–40, doi:10.1007/BF01200056, MR 1113533, archived from the original on 2012-03-31, retrieved 2011-10-02
^ Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi (2002), "In search of an easy witness: exponential time vs. probabilistic polynomial time" (PDF), Journal of Computer and System Sciences, 65 (4): 672–694, doi:10.1016/S0022-0000(02)00024-7, MR 1964649
^ 기하급수적 계층구조의 Karp-Lipton 붕괴에 관한 연구
^ 진이 카이.강의 11: P/폴리, 스파스 세트, 마하니의 정리.CS 810: 복잡성 이론 소개.위스콘신 대학 매디슨.2003년 9월 18일.
^ Adleman, L. M. (1978), "Two theorems on random polynomial time", Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pp. 75–83, doi:10.1109/SFCS.1978.37
^ 찰스 H. 베넷, 존 길랜덤 오라클 A에 대해 P ≠ NP^A^A ≠ co-NP^A 확률 1. [1]

[lutz93-1] Lutz, Jack H.; Schmidt, William J. (1993), "Circuit size relative to pseudorandom oracles", Theoretical Computer Science, 107 (1): 95–119, doi:10.1016/0304-3975(93)90256-S, MR 1201167

[2] "Lecture notes on computational complexity by Peter Bro Miltersen" (PDF). Archived from the original (PDF) on 2012-02-23. Retrieved 2009-12-25.

[3] 소수점 찾기 & 소수점 증명

[4] Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112

[5] Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer (1995), "If NP has polynomial-size circuits, then MA = AM", Theoretical Computer Science, 137 (2): 279–282, doi:10.1016/0304-3975(95)91133-B, MR 1311226

[6] Babai, László; Fortnow, Lance; Lund, Carsten (1991), "Nondeterministic exponential time has two-prover interactive protocols", Computational Complexity, 1 (1): 3–40, doi:10.1007/BF01200056, MR 1113533, archived from the original on 2012-03-31, retrieved 2011-10-02

[7] Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi (2002), "In search of an easy witness: exponential time vs. probabilistic polynomial time" (PDF), Journal of Computer and System Sciences, 65 (4): 672–694, doi:10.1016/S0022-0000(02)00024-7, MR 1964649

[8] 기하급수적 계층구조의 Karp-Lipton 붕괴에 관한 연구

[9] 진이 카이.강의 11: P/폴리, 스파스 세트, 마하니의 정리.CS 810: 복잡성 이론 소개.위스콘신 대학 매디슨.2003년 9월 18일.

[10] Adleman, L. M. (1978), "Two theorems on random polynomial time", Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pp. 75–83, doi:10.1109/SFCS.1978.37

[11] 찰스 H. 베넷, 존 길랜덤 오라클 A에 대해 P ≠ NP^A^A ≠ co-NP^A 확률 1. [1]

[1]

[2]

[3]

[4]

[6]

[7]

[9]

[10]

[11]

v t 중요 복잡성 클래스(추가)
실현 가능한 것으로 간주됨	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-완전 ZPP RP BPP BQP APX
실행 불가능한 것으로 의심됨	UP NP NP-완전 NP-하드 공동 NP 공동 NP-완전 AM QMA PH ⊕P PP #P #P-완전 IP 프스페이스 PSpace-완전
실현 불가능한 것으로 간주됨	엑스트라타임 NEXPTIME 엑스포스페이스 2-EXPTIME 초등 PR R RE 모두
클래스 계층	다항식 계층 구조 지수 계층 구조 그르제고르차이크 계층 구조 산술 계층 구조 부울 계층 구조
계급가족	디타임 NTIME 디스페이스 NSpace 확률적으로 확인할 수 있는 증거 인터랙티브 프루프 시스템

Search

P/폴리

네임스페이스

더

목차

형식 정의

P/폴리 중요도

경계 오류 확률론적 다항식이 P/poly에 포함되어 있음

증명

참조