Известно ли, что существуют функции со следующим свойством прямой суммы?

15

Этот вопрос может быть задан либо в рамках сложности схем булевых схем, либо в рамках теории алгебраической сложности, либо, вероятно, во многих других ситуациях. Подсчитав аргументы, легко показать, что на N входах существуют булевы функции, для которых требуется экспоненциально много гейтов (хотя, конечно, у нас нет явных примеров). Предположим, что я хочу оценить одну и ту же функцию M раз для некоторого целого числа M на M различных наборах входов, так что общее количество входов равно MN. То есть, мы просто хотим , чтобы оценить для однойтой же функцииFв каждый момент времени.f(Икс1,1,,,,,Икс1,N),е(Икс2,1,,,,,Икс2,N),,,,,е(ИксM,1,,,,,ИксM,N)е

Вопрос заключается в следующем: известно ли, что существует последовательность функций (одна функция для каждого N), такая, что для любого N, для любого M общее количество требуемых вентилей, по крайней мере, равно M, умноженному на экспоненциальную функцию N? Кажется, простой аргумент подсчета не работает, поскольку мы хотим, чтобы этот результат был справедлив для всех М. Можно придумать простые аналоги этого вопроса в теории алгебраической сложности и других областях.е

Мэтт Гастингс
источник

Ответы:

13

Что ж, это неверно: можно оценить M копий ЛЮБОГО f, используя только O (N (M + 2 ^ N)) вентилей, которые могут быть намного меньше, чем M * exp (N) (фактически, вы получаете линейную амортизацию сложность для экспоненциального M). Я не помню ссылку, но думаю, что она может выглядеть примерно так:

Сначала добавьте 2 ^ N фиктивных входных данных, которые являются просто константами 0 ... 2 ^ N-1, и теперь обозначим i-й N-битный вход через xi (поэтому для i <= 2 ^ N мы имеем xi = i, а для 2 ^ N <я <= 2 ^ N + M у нас есть оригинальные входы). Теперь мы создадим триплет для каждого из входов M + 2 ^ N: (i, xi, fi) где fi - это f (i) для первых 2 ^ N входов (постоянная, встроенная в схему) и fi = "*" в противном случае. Теперь мы сортируем триплеты (i, xi, fi) по ключу xi, и пусть j-й триплет будет (i_j, x_j, f_j) из этого, мы вычисляем триплет (i_j, x_j, g_j), позволяя g_j быть f_j, если f_j не является "*", и пусть g_j будет g_ (j-1) в противном случае. Теперь отсортируйте новые триплеты обратно по ключу i_j, и вы получите правильные ответы в правильных местах.

Ноам
источник
Умная! Одна небольшая вещь: мы должны отсортировать триплеты стабильно (или в каком-то другом методе, который гарантирует, что триплеты с fi ≠ « » появятся раньше, чем триплеты с fi = « »).
Цуёси Ито
Очень умно, и спасибо. Работает ли что-то подобное в условиях алгебраической сложности или нет?
Мэтт Гастингс
1
Я думаю, что другой способ сказать это в случае, когда M уходит в бесконечность, это то, что вы можете потратить 2 ^ N * 2 ^ N времени на создание хеш-таблицы для всех значений f, а затем вы можете вычислить каждую копию в O (N Время Я думаю, что есть еще одна причина, по которой мы, по крайней мере, не должны знать, верно ли что-то подобное, даже для более мягких значений N, а именно, что это даст лучше, чем известные нижние границы. Вы могли бы построить функцию с суперлинейной нижней границей с помощью первого грубого принуждения, чтобы найти функцию на входах n '= log n (или, возможно, n' = loglog n) с большой сложностью, а затем взять n / n'копии этого ,
Вооз Барак
1
В рассмотренном выше аргументе о том, почему такие результаты приводят к нижним пределам, я не знаю, действительно ли количество повторений меньше, но оно применимо и к бесконечным полям.
Вооз Барак
Привет Боаз, На самом деле ваш комментарий именно поэтому я был заинтересован в существовании этих функций. Тем не менее, есть тонкий момент, "грубое принуждение". Может быть (что и было целью моего вопроса), что такие функции существуют, но у нас нет алгоритма, который позволил бы нам продемонстрировать, что данная функция обладает этим свойством. В конце концов, кажется, нет способа грубо форсировать свойство, которое имеет такая нижняя граница для всех M, потому что вам придется проверять бесконечное число различных цепей. Так что, возможно, такие функции существуют для бесконечных полей, но мы не можем это показать.
Мэтт Гастингс
10

О(2N/N)ммем2N/N

«Сети, вычисляющие логические функции для нескольких входных значений»

мзнак равно2о(N/журналN)меО(2N/N)мзнак равно1

Я не могу найти в интернете неоткрытую копию или домашнюю страницу для автора, но я наткнулся на статью в этом процессе:

Сложность булевой функции (серия лекций Лондонского математического общества)

Энди Друкер
источник
Благодарность! Не было ли вопроса, который задавался о парадоксах в TCS? Это также может послужить ответом там :)
Арнаб
Спасибо за этот ответ тоже. Будучи не в состоянии прочитать материалы, я думаю, что, как и в предыдущем ответе, он может опираться на конечное число возможных входных данных, так что опять тот же дополнительный вопрос, что и выше: как насчет случая алгебраической сложности?
Мэтт Гастингс
На самом деле, похоже, что Шеннон впервые доказал верхнюю оценку O (2 ^ n / n); Лупанов получил правильную ведущую константу. Я исправил это. Подробности объясняются в «Пересмотре границ на размер схемы самых сложных функций», Frandsen и Miltersen.
Энди Друкер
5

Что касается алгебраической сложности, я не знаю примера, в котором экспоненциальная сложность сводится к субэкспоненциальной амортизированной сложности, но, по крайней мере, есть простой пример того, что сложность M непересекающихся копий может быть значительно меньше, чем M раз сложности одной копии. :

Для «случайной» n * n матрицы A сложность билинейной формы, определенной как A, (функция f_A (x, y) = xAy, где x и y - 2 вектора длины n) равна Omega (n ^ 2 ) - это может быть показано аргументом измерения «как в подсчете», так как вам нужно n ^ 2 «мест» в схеме для помещения констант. Однако, учитывая n различных пар векторов (x ^ 1, y ^ 1) ... (x ^ n, y ^ n), вы можете поместить x в строки n * n матрицы X, и аналогично y в столбцы матрицы Y, а затем прочитайте все ответы x ^ iAy ^ i с диагонали XAY, где это вычисляется в n ^ 2.3 (или около того) операциях с использованием быстрого умножения матриц, значительно меньше, чем n * n ^ 2.

Ноам
источник
Спасибо, я знаю этот пример. Аналогичным является то, что существуют полиномы степени n от одной переменной, для оценки которых в данной точке требуется время n (хотя я не думаю, что есть какие-либо явные примеры, я ошибаюсь?) Однако такой полином можно оценить в n моментов времени n log ^ 2 (n).
Мэтт Гастингс
1
Я нашел две работы из 80-х по алгебраической задаче прямой суммы: «О справедливости гипотезы прямой суммы» Джаджи и Такче и «О расширенной гипотезе прямой суммы» Бшути. Я не могу обобщить их содержание, но, возможно, они будут полезны.
Энди Друкер
5

Это было изучено и решено Вольфгангом Полом, который показал, по существу, то, что обсуждается.

Дик Липтон
источник
2
Ницца! Есть какая-нибудь ссылка?
Сянь-Чжи Чан 張顯 之