깊이 lg n 의 다항식 크기 ​​(언 바운드 팬인) 회로로 비트 임계 값 게이트를 계산할 수 있습니까?n

$n$ ? 또는이 회로를 사용하여 입력 비트에서 1의 수를 계산할 수 있습니까?lgnlglgn

$\frac{\lg n}{\lg \lg n}$

는 ?TC0⊆AltTime(O(lgnlglgn),O(lgn))

$\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg \lg n}), O(\lg n))$

참고 . 임계 값 게이트를 계산할 때 회로 깊이에서 lg lg n 인자를 절약 할 수 있는지 묻는 것이 본질적으로 문제입니다 .T C0⊆ N C1= A L o g T i m e = A l t T i m e ( O ( lgn ) , O ( lgn ) )

$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$lglg엔

$\lg \lg n$

편집하다:

Kristoffer가 그의 답변에 썼 듯이 우리는 factor를 구할 수 있습니다 . 하지만 조금 더 절약 할 수 있습니까? O 를 대체 할 수 있습니까 ( lg nlglg엔

$\lg \lg n$와O(LGNO ( lg엔lglg엔)

$O(\frac{\lg n}{\lg \lg n})$?o ( lg엔lglg엔)

$o(\frac{\lg n}{\lg \lg n})$

계층화 된 무차별 트릭은 (보다 일반적으로 lg lg n + ω ( 1 )의 모든 기능) 을 저장하는 데 작동하지 않는 것 같습니다 .2 개 lglg엔

$2 \lg \lg n$lglgn+ω(1)

$\lg \lg n + \omega(1)$

답변