Рассмотрим функцию вычисляется с помощью булевой схемы C с п входами размера сек ( п ) = р ø л у ( п ) в базисе { Х О Р , Н Д , Н О Т } (с полустепень захода 2 для X O R , A N D ворота).
Булева схема является слоистой, если она может быть размещена в слоях ( d - глубина схемы) вентилей, так что любой край между двумя вентилями соединяет смежные слои.
Учитывая, что имеет логическую схему размера s , что мы можем сказать о размере многоуровневой схемы, вычисляющей f ? Существует тривиальная верхняя граница: добавляя фиктивные узлы к C на каждом слое, пересекаемом ребром, мы получаем многослойную схему размером не более O ( s 2 ) . Но можем ли мы стать лучше вообще (например, O ( s ⋅ log s ) или O ( s ) ), или для интересного класса цепей?
Фон. Этот вопрос вытекает из недавних результатов в криптографии, которые показывают, как безопасно вычислять многоуровневые логические схемы размера с помощью связи o ( s ) (например, s / log s или s / log log s ) ; Я пытаюсь понять, насколько ограничительным может быть это ограничение для слоистых логических схем на практике, как для общих схем, так и для «естественных» схем. Тем не менее, я не нашел много информации о слоистых схемах в литературе; соответствующие указатели также приветствуются.
источник
Ответы:
Насколько я знаю, три класса слоистых схем были изучены. Во всех этих определениях дуги допускаются только между двумя смежными слоями.
Схема называется синхронной ( Harper, 1977 ), если все шлюзы расположены в слоях, а входы должны быть на уровне 0. (Эквивалентное определение: для любого вентиляg все пути от входов до g имеют одинаковую длину.)
Схема является локально синхронной ( Белага 1984 ), если каждый вход происходит ровно один раз, но на произвольном уровне.
Схема является многоуровневой ( Gál, Jang 2010 ), если ворота и входы организованы в слои, входы могут возникать несколько раз на разных уровнях. (Эквивалентное определение: для любого вентиляg и выходного вентиля o все направленные пути от g до o имеют одинаковую длину.)
Легко видеть, что три класса перечислены от самого слабого до самого сильного (а класс неограниченных цепей еще сильнее).
Что касается размера многоуровневой схемы, вычисляющей неограниченную схему размераs мы знаем следующее:
Существуют явные функции
источник