Этот вопрос может быть задан либо в рамках сложности схем булевых схем, либо в рамках теории алгебраической сложности, либо, вероятно, во многих других ситуациях. Подсчитав аргументы, легко показать, что на N входах существуют булевы функции, для которых требуется экспоненциально много гейтов (хотя, конечно, у нас нет явных примеров). Предположим, что я хочу оценить одну и ту же функцию M раз для некоторого целого числа M на M различных наборах входов, так что общее количество входов равно MN. То есть, мы просто хотим , чтобы оценить для однойтой же функцииFв каждый момент времени.
Вопрос заключается в следующем: известно ли, что существует последовательность функций (одна функция для каждого N), такая, что для любого N, для любого M общее количество требуемых вентилей, по крайней мере, равно M, умноженному на экспоненциальную функцию N? Кажется, простой аргумент подсчета не работает, поскольку мы хотим, чтобы этот результат был справедлив для всех М. Можно придумать простые аналоги этого вопроса в теории алгебраической сложности и других областях.
источник
«Сети, вычисляющие логические функции для нескольких входных значений»
Я не могу найти в интернете неоткрытую копию или домашнюю страницу для автора, но я наткнулся на статью в этом процессе:
Сложность булевой функции (серия лекций Лондонского математического общества)
источник
Что касается алгебраической сложности, я не знаю примера, в котором экспоненциальная сложность сводится к субэкспоненциальной амортизированной сложности, но, по крайней мере, есть простой пример того, что сложность 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.
источник
Это было изучено и решено Вольфгангом Полом, который показал, по существу, то, что обсуждается.
источник