편집 (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 회로 로 변환 하는 방법이 있다는 것을 의미합니까 ? 그렇다면 어떻게이 작업을 수행하며 이것이 가장 잘 알려진 방법입니까?
원래 질문 :
깊이 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/log2S)
S=O(n)
exp(n/logn)
F
F′
M=O(S2A)
D
F′
D=O(logM)=O(AlogS)
D≤1.73log2M
Depth=O(Size/logSize)
A
S/log2S
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(DlogS)
f
AC0
k
S
f
D≤k−1+⌈log2S⌉
D≤klogS
logS