Можем ли мы вычислить битный пороговый вентиль по схемам с полиномиальным размером (неограниченным разветвлением) глубиной lg n ? В качестве альтернативы, мы можем посчитать число 1 во входных битах, используя эти схемы?
Является ли ?
Заметим , что . Таким образом, вопрос, по сути, заключается в том, можем ли мы сохранить коэффициент lg lg n в глубине цепей при вычислении пороговых значений.
Редактировать:
Как писал Кристоффер в своем ответе, мы можем сохранить фактор . Но можем ли мы сэкономить немного больше? Можем ли мы заменить O ( LG NсO(LGN?
Мне кажется, что многослойный трюк с грубой силой не работает для сохранения даже (в общем, любой функции в lg lg n + ω ( 1 ) ).
Ответы:
Рассмотрим схему Fanin 2 из глубины O ( журнал п ) . Разделите слои C на O ( log n / log log n ) блоков каждого из log log n последовательных слоев. Теперь мы хотим заменить каждый блок схемой глубины 2. А именно, каждый шлюз в последнем слое блока зависит не более чем от 2 log log n = log nC O(logn) C O(logn/loglogn) loglogn 2loglogn=logn ворота последнего слоя в блоке ниже. Таким образом, мы можем заменить каждый вентиль в последнем слое на DNF полиномиального размера с входами, которые являются воротами в последнем слое блока ниже. Делая это для всех ворот в последних слоях для всех блоков и соединяя их, вы получите желаемую схему.
Позвольте мне отметить, что это, по сути, лучшее, что можно получить: лемма о переключении допускает нижние оценки вплоть до глубины .logn/loglogn
источник