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

⊆

⊆

⊆

n

n

n

n

n

n

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

⊆

P / poly를 까?

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

⊆

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

[ADDED 08.10.2017] : BPP ⊈

⊈

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

[2O(n)]

2o(n)

2o(n)

. 이 결과를 상기시켜 준 Ryan에게 감사합니다.

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

⊆

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

{0,1}∗

0

0

1

1

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

⊆

---

참고 [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:X→Y

f:X→Y

v

v

f1,…,fv

f1,…,fv

F

F

S⊆{1,…,v}

S⊆{1,…,v}

(x,y)∈X×Y

(x,y)∈X×Y

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

fi(x)=y

i∈S

i∈S

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

x∈X

f∈F

f∈F

F

F

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

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

c>0

c>0

f(x)

f(x)

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

x∈X

m=O(v)

m=O(v)

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:Rn→R

f:Rn→R

≤s

≤s

F

F

D=2s

D=2s

F

F

O(nlogD)=O(ns)

O(nlog⁡D)=O(ns)

⊆

⊆

산술 회로를위한 P / poly.

---

---

답변