게이트 팬 아웃 1을 사용 하여 각 게이트에 팬 아웃 1이있는 경우 (즉,

편집 (2011 년 8 월 22 일) :

나는 질문을 더 단순화하고 질문에 현상금을 넣습니다. 아마도이 간단한 질문에 쉽게 대답 할 수 있습니다. 또한 더 이상 관련이없는 원래 질문의 모든 부분을 취소 할 것입니다. (Stasys Jukna와 Ryan O’Donnell에게 원래 질문에 부분적으로 답변 해 주셔서 감사합니다!)


배경:

깊이 k 및 크기 S를 갖는 AC 0 회로가 주어지면 , 새로운 회로가 모든 게이트에 대해 팬 아웃 = 1을 갖도록 깊이 k 및 크기 O ( S k ) 와 동일한 기능을 계산하는 다른 AC 0 회로 가 존재한다 . 다시 말해, 회로는 트리처럼 보입니다 (입력은 둘 이상의 게이트로 팬 아웃 될 수 있으므로 입력 제외). 이를 수행하는 한 가지 방법은 모든 게이트가 팬 아웃 = 1이 될 때까지 팬 아웃> 1이있는 모든 게이트를 복제하는 것입니다.

O(Sk)

그러나 이것은 AC 변환하는 가장 효율적인 방법입니다 0 AC에 회로를 0 팬 아웃 1 회로? Ryan O’Donnell의 강의 노트 14 장 에서 다음을 읽었습니다 .

C가 패리티를 계산하는 크기 S의 깊이 k 회로라고 가정하십시오. 레벨이 AND 및 OR 게이트를 번갈아 가며, 입력 와이어가 2n 리터럴이고 각 게이트에 팬 아웃 1이있는 경우 (즉, 트리 임) ) – 및 최대의 크기가 증가 .

(2kS)2≤O(S4)

각주 : 실제로, 이것은 약간 까다로운 운동입니다. 크기 만 가져야하는 것이 더 쉽습니다. k를 “일정한”것으로 생각하면 우리의 목적과 거의 동일합니다.

O(Sk)

이것은 크기 S의 깊이 k AC 0 회로 를 취해 팬 아웃 1, 깊이 k 및 크기 ( 2 k S ) 2 를 갖는 AC 0 회로 로 변환 하는 방법이 있다는 것을 의미합니까 ? 그렇다면 어떻게이 작업을 수행하며 이것이 가장 잘 알려진 방법입니까?

(2kS)2

원래 질문 :

깊이 k와 크기 S를 가진 AC 0 회로가 주어지면 이것을 깊이 k와 게이트 팬 아웃 1 의 AC 0 회로 로 변환하는 가장 잘 알려진 방법은 무엇입니까 (결과 회로의 회로 크기 최소화 측면에서) ? 이것으로 알려진 하한이 있습니까?


더 새롭고 간단한 질문 :

이 질문은 결과 회로가 일정한 깊이라고 주장하지 않는 원래 질문을 완화합니다. 상술 한 바와 같이, 깊이 k, 크기 S를 갖는 AC 0 회로를 크기 를 갖는 회로로 변환 하여 새로운 회로가 모든 게이트에 대해 팬 아웃 = 1이되도록하는 방법이있다. 더 나은 구조가 있습니까?

O(Sk)

깊이 k와 크기 S 의 AC 0 회로가 주어지면 게이트 팬 아웃 1을 사용하여 깊이 회로로 변환하는 가장 잘 알려진 방법은 무엇입니까 (결과 회로의 회로 크기 최소화 측면에서)?



답변

이전 의견을 요약하려고합니다.

k

S

A

S

F

O(SA)

A=O(S/log2⁡S)

S=O(n)

exp⁡(n/log⁡n)

F

F′

M=O(S2A)

D

F′

D=O(log⁡M)=O(Alog⁡S)

D≤1.73log2⁡M

Depth=O(Size/log⁡Size)

A

S/log2⁡S

k

A=k

A=k−1

k=3

S

S2

? 나는 대답이 “아니오”여야한다고 생각한다 (학생들에게는 흥미로운 연습이 될 수있다). 깊이 3 공식은 CNF의 큰 OR입니다. 문제는 공통적으로 많은 절을 공유하지만 CN-3의 OR을 찾아서 깊이 3 공식을 강요하기 위해 “매우 다르다”는 것입니다.

S

D

3S−2n

2D

O(S2)

O(Dlog⁡S)

f

AC0

k

S

f

D≤k−1+⌈log2⁡S⌉

D≤klog⁡S

log⁡S