Можем ли мы рассчитывать на глубину

19

Можем ли мы вычислить битный пороговый вентиль по схемам с полиномиальным размером (неограниченным разветвлением) глубиной lg nn ? В качестве альтернативы, мы можем посчитать число 1 во входных битах, используя эти схемы?lgnlglgn

Является ли ?TC0AltTime(O(lgnlglgn),O(lgn))


Заметим , что . Таким образом, вопрос, по сути, заключается в том, можем ли мы сохранить коэффициент lg lg n в глубине цепей при вычислении пороговых значений.TC0NC1=ALogTime=AltTime(O(lgn),O(lgn))lglgn


Редактировать:

Как писал Кристоффер в своем ответе, мы можем сохранить фактор . Но можем ли мы сэкономить немного больше? Можем ли мы заменить O ( LG NlglgnсO(LGNO(lgnlglgn)?o(lgnlglgn)

Мне кажется, что многослойный трюк с грубой силой не работает для сохранения даже (в общем, любой функции в lg lg n + ω ( 1 ) ).2lglgnlglgn+ω(1)

Кава
источник
3
Я изменил свой ответ, чтобы также включить последние изменения.
Кристоффер Арнсфельт Хансен

Ответы:

22

Рассмотрим схему Fanin 2 из глубины O ( журнал п ) . Разделите слои C на O ( log n / log log n ) блоков каждого из log log n последовательных слоев. Теперь мы хотим заменить каждый блок схемой глубины 2. А именно, каждый шлюз в последнем слое блока зависит не более чем от 2 log log n = log nCO(logn)CO(logn/loglogn)loglogn2loglogn=lognворота последнего слоя в блоке ниже. Таким образом, мы можем заменить каждый вентиль в последнем слое на DNF полиномиального размера с входами, которые являются воротами в последнем слое блока ниже. Делая это для всех ворот в последних слоях для всех блоков и соединяя их, вы получите желаемую схему.

Позвольте мне отметить, что это, по сути, лучшее, что можно получить: лемма о переключении допускает нижние оценки вплоть до глубины .logn/loglogn

Кристоффер Арнсфельт Хансен
источник
1
Спасибо Кристоффер. Я добавил немного более сильный вопрос.
Каве
2
Просто чтобы убедиться, что я правильно общую картину: до глубины lg n / lg lg n эти схемы не могут вычислить четность, на этой глубине они внезапно становятся способными вычислять N C 1 . lgn/lglgnNC1
Каве
2
Это верно (до постоянных факторов в глубине).
Кристоффер Арнсфельт Хансен