Насколько мала может быть слоистая логическая схема для функции со сложностью схемы

12

Рассмотрим функцию вычисляется с помощью булевой схемы C с п входами размера сек ( п ) = р ø л у ( п ) в базисе { Х О Р , Н Д , Н О Т } (с полустепень захода 2 для X O R , A N D ворота).fCns(n)=poly(n){XOR,AND,NOT}XOR,AND

Булева схема является слоистой, если она может быть размещена в слоях ( d - глубина схемы) вентилей, так что любой край между двумя вентилями соединяет смежные слои.dd

Учитывая, что имеет логическую схему размера s , что мы можем сказать о размере многоуровневой схемы, вычисляющей f ? Существует тривиальная верхняя граница: добавляя фиктивные узлы к C на каждом слое, пересекаемом ребром, мы получаем многослойную схему размером не более O ( s 2 ) . Но можем ли мы стать лучше вообще (например, O ( s log s ) или O ( s ) ), или для интересного класса цепей?fsfCO(s2)O(slogs)O(s)

Фон. Этот вопрос вытекает из недавних результатов в криптографии, которые показывают, как безопасно вычислять многоуровневые логические схемы размера с помощью связи o ( s ) (например, s / log s или s / log log s ) ; Я пытаюсь понять, насколько ограничительным может быть это ограничение для слоистых логических схем на практике, как для общих схем, так и для «естественных» схем. Тем не менее, я не нашел много информации о слоистых схемах в литературе; соответствующие указатели также приветствуются.so(s)s/logss/loglogs)

Жоффруа Коуто
источник
4
Вот пример схемы, которую сложно преобразовать в многоуровневую схему без значительного увеличения размера. Определите как некоторую функцию, которая может быть вычислена в размере u . Определите g ( x 1 , , x n ) = ( x 2 , , x n , x 1f ( x 2 ,f:{0,1}n1{0,1}u , и пусть C будет т Итерации г . Тогда C имеет размер O ( t u ) . Кажется, трудно построить многоуровневую схему с размером менее Θ ( n t ) . Таким образом, если u = o ( n ) , возможно, нам следует ожидать разрыва между размером схемы и размером многоуровневой схемы. Не доказательство, просто наводящий пример, чтобы стимулировать интуицию. g(x1,,xn)=(x2,,xn,x1f(x2,,xn))CtgCO(tu)Θ(nt)u=o(n)
DW
2
Насколько я помню, для слоистых цепей самая известная нижняя граница имеет вид . Это особенно легко доказать для функции n- to- n . Возьмем, например, линейное отображение A x, где A { 0 , 1 } n × n имеет нули только на главной диагонали. Тогда на каждом слое должно быть не менее n вентилей, а количество слоев не менее log 2 n . Обратите внимание, что эта функция может быть легко вычислена с помощью обычной схемы размера O (Ω(nlogn)nnAxA{0,1}n×nnlog2n . Для функций с одним выходом также возможно доказать ту же нижнюю границу, но я не помню аргумента. O(n)
Александр Сергеевич Куликов
1
Большое спасибо за комментарии. @ AlexanderS.Kulikov, твой аргумент фольклорный, или у тебя есть какой-то указатель на работы над многослойными схемами? имеет смысл - я был бы очень удивительно , что - то меньше , - но это O ( п 2 ) единственная известная верхняя граница? Ω(nlogn)O(n2)
Жоффруа Куто
1
Я думаю, это фольклор, да. Я не уверен, что получил вопрос о верхней границе . Вы можете взглянуть на следующую статью: cs.utexas.edu/~panni/sizedepth.pdfO(n2)
Александр Сергеевич Куликов,
1
Я думаю, что мы не знаем преобразования лучше, чем в целом. Обратите внимание, что схема размером s и глубиной d может быть преобразована в слоистую схему размером не более d s . (Что в худшем случае дает нам схему размером O ( s 2 ) .) Я просто хотел бы отметить, что если бы мы могли доказать нижнюю границу ω ( n log n ) для размера слоистой схемы, это дайте нам суперлинейную нижнюю границу размера схем логарифмической глубины для этой функции. Этот вопрос остается открытым более 40 лет.O(s2)sddsO(s2)ω(nlogn)
Алексей Головнев

Ответы:

8

Насколько я знаю, три класса слоистых схем были изучены. Во всех этих определениях дуги допускаются только между двумя смежными слоями.

  1. Схема называется синхронной ( Harper, 1977 ), если все шлюзы расположены в слоях, а входы должны быть на уровне 0. (Эквивалентное определение: для любого вентиля g все пути от входов до g имеют одинаковую длину.)

  2. Схема является локально синхронной ( Белага 1984 ), если каждый вход происходит ровно один раз, но на произвольном уровне.

  3. Схема является многоуровневой ( Gál, Jang 2010 ), если ворота и входы организованы в слои, входы могут возникать несколько раз на разных уровнях. (Эквивалентное определение: для любого вентиля g и выходного вентиля o все направленные пути от g до o имеют одинаковую длину.)

Легко видеть, что три класса перечислены от самого слабого до самого сильного (а класс неограниченных цепей еще сильнее).

Что касается размера многоуровневой схемы, вычисляющей неограниченную схему размера s мы знаем следующее:

  1. ss2

  2. ω(slogs)sdO(sd)fω(nlogn)fO(logn)O(n)

  3. Существуют явные функции

    Ω(nlogn)O(n)

    Ω(nlogn)O(n)

n

f:{0,1}n{0,1}niiO(n)lognnnfΩ(nlogn)n1Ω(logn)nn

Алекс Головнев
источник