깊이 lg n 의 다항식 크기 (언 바운드 팬인) 회로로 비트 임계 값 게이트를 계산할 수 있습니까?
? 또는이 회로를 사용하여 입력 비트에서 1의 수를 계산할 수 있습니까?
는 ?
참고 . 임계 값 게이트를 계산할 때 회로 깊이에서 lg lg n 인자를 절약 할 수 있는지 묻는 것이 본질적으로 문제입니다 .
편집하다:
Kristoffer가 그의 답변에 썼 듯이 우리는 factor를 구할 수 있습니다 . 하지만 조금 더 절약 할 수 있습니까? O 를 대체 할 수 있습니까 ( lg n
와O(LGN
?
계층화 된 무차별 트릭은 (보다 일반적으로 lg lg n + ω ( 1 )의 모든 기능) 을 저장하는 데 작동하지 않는 것 같습니다 .
답변
깊이 O ( log n ) 의 fanin 2 회로를 고려하십시오 . C 의 레이어 를 O 로 나눕니다 ( log n / log log
각 log log n 연속 레이어가차단됩니다. 이제 각 블록을 깊이 2 회로로 교체하려고합니다. 즉, 블록의 마지막 레이어에있는 각 게이트는 최대 2 log log n = log n에 의존합니다
아래 블록에서 마지막 레이어의 게이트. 따라서 마지막 레이어의 각 게이트를 다항식 크기의 DNF로 대체 할 수 있습니다. 입력은 아래 블록의 마지막 레이어의 게이트입니다. 모든 블록의 마지막 레이어에서 모든 게이트에 대해 이것을 수행하고 이들을 연결하면 원하는 회로가 생성됩니다.
스위칭 보조 정리 하한에 대한 깊이있는 모든 방법 수 있습니다 : 나이 본질적으로 얻을 수있는 최선의 하나입니다주의합시다 .