우리는 BPP ⊆ P / poly 및 훨씬 더 강한 BPP / poly ⊆ P / poly 가 포함된다는 것을 알고 있습니다 (현재 약 40 년 동안 Adleman, Bennet 및 Gill에게 감사드립니다) . “/ poly”는 우리가 불균일하게 (각 입력 길이 n 에 대해 별도의 회로) 일한다는 것을 의미하고 , 이 “/ poly”가없는 P 는 가능한 모든 입력 길이 n에 대해 하나의 Turing 머신을 가지고 있음을 의미 합니다 . n = 다음 “빅뱅”까지의 시간 (초)입니다. ⊆

$\subseteq$

$\subseteq$ ⊆

$\subseteq$

$\subseteq$ n

$n$

$n$n

$n$

$n$n

$n$

$n$

질문 1 : 증명 (또는 반증) 어떤 새로운 것 BPP = P는 우리가 알고있는 후 우리의 지식에 기여 BPP를 ⊆

$\subseteq$

$\subseteq$ P / poly를 까?

“새로운”이란 다른 복잡한 클래스의 축소 / 분리와 같은 놀라운 결과를 의미합니다. 이것을 NP ⊆

$\subseteq$

$\subseteq$ P / poly 의 증명 / 비방이 가져올 결과와 비교하십시오 .

[ADDED 08.10.2017] : BPP ⊈

$⊈$

$\not\subseteq$ P 의 놀라운 결과 중 하나 는 Impagliazzo와 Wigderson 에서 볼 수 있듯이 E = DTIME [ 2 O ( n ) ]의 모든 (!) 문제
는 크기가 2 o ( n )[2O(n)]

$[2^{O(n)}]$

$[2^{O(n)}]$2o(n)

$2^{o(n)}$

$2^{o(n)}$ . 이 결과를 상기시켜 준 Ryan에게 감사합니다.

질문 2 : 왜 BPP / poly ⊆ P / poly
의 증거와 유사한 선을 따라 BPP = P 를 증명할 수 없습니까?
⊆

$\subseteq$

$\subseteq$

하나의 “명백한”장애물은 유한 대 무한 도메인 문제 : 부울 회로가 이상 작동 유한 튜링 기계가 이상 전체 세트 작업 반면, 도메인 의 0 – 1 길이의 문자열을. 따라서, 확률 론적 부울 회로를 비 무작위 화하기 위해서는, 확률 론적 회로의 독립된 사본 대부분을 취하고 체 르노 프의 불평등을 노동 조합과 함께 적용하는 것으로 충분하다. 물론, 무한 도메인에 대해서는이 단순한 다수 규칙이 적용되지 않습니다.
{0,1}∗

$\{0,1{\}}^{\ast }$

$\{0,1\}^*$0

$0$

$0$1

$1$

$1$

그러나 이것이 (무한 도메인) 실제 “장애”입니까? 통계 학습 이론 (VC 차원)의 결과를 사용함으로써, 우리는 이미 BPP / poly over P / poly가 산술 회로 (모든 실수에 대해 작동)와 같은 무한 영역에서 작동하는 회로에도 적용됨을 증명할 수 있습니다 . 예를 들어 Cucker의이 논문을 참조하십시오 .
비슷한 접근 방식을 사용할 때, 폴리-타임 튜링 머신의 VC 치수가 너무 클 수 없다는 것을 보여 주기만하면됩니다. 후자 단계를 시도한 사람이 있습니까?
⊆

$\subseteq$

$\subseteq$

---

참고 [2017년 7월 10일 추가] derandomization의 맥락에서, 클래스의 VC 치수
함수 F : X → Y가 최대 숫자로 정의된다 V 기능이 존재하는 f를 (1) , … , F (V) 에서 F 이러한 즉 모든 위해 S ⊆ { 1 , … , V } 포인트가 ( X , Y ) ∈ X × Y 와
F I ( XF

$F$

$F$f:X→Y

$f:X\to Y$

$f:X\to Y$v

$v$

$v$f1,…,fv

$f_1,\dots ,f_v$

$f_1,\ldots,f_v$F

$F$

$F$S⊆{1,…,v}

$S\subseteq \{1,\dots ,v\}$

$S\subseteq\{1,\ldots,v\}$(x,y)∈X×Y

$(x,y)\in X\times Y$

$(x,y)\in X\times Y$ IFF I ∈ S . 즉, 함수를 통해 포인트 세트가 아니라 포인트를 통해 함수 세트를 산산조각냅니다. VC 차원의 두 가지 결과 정의는 관련되어 있지만 지수 적으로 관련됩니다.fi(x)=y

$f_i(x)=y$

$f_i(x)=y$i∈S

$i\in S$

$i\in S$

결과는 (알려진 확률이 균일 수렴 ) 후 다음을 의미한다 : 만약 각 입력 , 임의로 고른 함수 F ∈ F (일부 확률 분포 하에서 F 를 만족하는) P의 R O B { F ( X ) = F ( X ) } ≥ 1 / 2 + C
상수에 대한 C > 0 , 다음 f를 ( X ) 에서 계산 될 수 있는 모든x∈X

$x\in X$

$x\in X$f∈F

$\mathbf{f}\in F$

$\mathbf{f}\in F$F

$F$

$F$Prob{f(x)=f(x)}≥1/2+c

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\{\mathbf{f}(x)=f(x)\}\ge 1/2+c$

$\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$c>0

$c>0$

$c>0$f(x)

$f(x)$

$f(x)$ 의 입력 일부 대다수로서 m = O ( V ) (고정)의 함수 F . 예를 들어Haussler의 논문의 Corollary 2를참조하십시오. [이를 유지하기 위해 F 에 약간의 측정 가능 조건이 있습니다.]
x∈X

$x\in X$

$x\in X$m=O(v)

$m=O(v)$

$m=O(v)$F

$F$

$F$F

$F$

$F$

예를 들어, 모든 다항식의 집합이다 F : R은 N → R 계산 가능한 연산 회로의 크기가 ≤ S 후 모든 다항식 F가 최대 과정 D = (2 개) 들 . (예를 참조 다항식 제로 패턴의 수에 공지 된 상한을 이용하여 본 연구 ), 하나의 VC 차원 것을 보여줄 수 F는 이고 O ( N 로그 D를 ) = O ( N (S) ) . 이것은 BPP / poly 포함을 의미합니다F

$F$

$F$f:Rn→R

$f:{\mathbb{R}}^n\to \mathbb{R}$

$f:\mathbb{R}^n\to\mathbb{R}$≤s

$\le s$

$\leq s$F

$F$

$F$D=2s

$D=2^s$

$D=2^s$F

$F$

$F$O(nlogD)=O(ns)

$O(n\log D)=O(ns)$

$O(n\log D)=O(ns)$⊆

$\subseteq$

$\subseteq$ 산술 회로를위한 P / poly.

---

---

답변