편집 (2011 년 8 월 22 일) :

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

배경:

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

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

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

(2kS)2≤O(S4)

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

O(Sk)

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

원래 질문 :

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

더 새롭고 간단한 질문 :

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

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

답변