Оцените логическую схему на партии аналогичных входов

Предположим, у меня есть логическая схема $C$ это вычисляет некоторую функцию $f:\{0,1\}^n \to \{0,1\}$, Предположим, что схема состоит из логических элементов И, ИЛИ и НЕ с максимальным и минимальным разветвлениями 2.

Позволять $x \in \{0,1\}^n$быть заданным входом. Данный$C$ а также $x$Хочу оценить $C$ на $n$ входы, которые отличаются от $x$ в позиции одного бита, т. е. для вычисления $n$ ценности $C(x^1),C(x^2),\dots,C(x^n)$ где $x^i$ такой же как $x$ кроме того, что его $i$этот бит перевернут.

Есть ли способ сделать это более эффективным, чем независимая оценка? $C$ $n$ раз на $n$ разные входы?

Предполагать $C$ содержит $m$ворота. Затем самостоятельно оценивая$C$ на все $n$ входы будут принимать $O(mn)$время. Есть ли способ вычислить$C(x^1),C(x^2),\dots,C(x^n)$ в $o(mn)$ время?

Необязательный контекст: если бы у нас была арифметическая схема (чьи ворота - умножение, сложение и отрицание) над$\mathbb{R}$тогда можно было бы вычислить $n$ производные по направлению ${\partial f \over \partial x_i}(x)$ в $O(m)$время. В принципе, мы могли бы использовать стандартные методы для вычисления градиента (правило обратного распространения / цепочки), в$O(m)$время. Это работает, потому что соответствующая функция непрерывна и дифференцируема. Мне интересно, можно ли сделать нечто подобное для логических схем. Булевы схемы не являются непрерывными и дифференцируемыми, поэтому вы не можете сделать то же самое, но, может быть, есть какой-то другой умный метод, который можно использовать? Может быть, какой-то трюк Фурье или что-то?

(Вариант вопроса: если у нас логические вентили с неограниченным разветвлением и ограниченным разветвлением, можете ли вы сделать асимптотически лучше, чем оценка $C$ $n$ раз?)

Я считаю маловероятным, что такой трюк легко найти и / или даст вам значительный выигрыш, поскольку он даст нетривиальные алгоритмы выполнимости. Вот как:

Прежде всего, хотя якобы проще, ваша проблема может на самом деле решить более общую проблему, учитывая схему $C$ а также $N$ входные $x_0, \ldots, x_{N-1}$оценить $C$ на всех входах быстрее, чем $\tilde{O}(N\cdot|C|)$время. Причина в том, что мы можем настроить$C$ в цепь $C'$ размера $|C| + \tilde{O}(Nn)$ который на входе $0^i10^{N-1-i}$, выходы $C(x_{i})$, По сути, мы просто создаем небольшую таблицу поиска, которая отправляет$0^i10^{N-1-i}$ в $x_i$и подключите его к $C$,

Нетривиальные алгоритмы для пакетной оценки булевых схем могут затем использоваться для создания быстрых алгоритмов выполнимости. Вот пример в простом случае, когда мы предполагаем, что у нас есть алгоритм, выполняющий оценку во времени$\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$ для любой постоянной $\epsilon > 0$, На входе цепь$C$мы можем решить удовлетворяемость путем расширения $C$ в цепь $C'$ размера $2^{n/2}\cdot |C|$ который является просто ИЛИ над всеми возможными вариантами первого $n/2$ входы в $C$(оставляя другие входы свободными). Затем мы проводим пакетную оценку$C'$ на всем своем $2^{n/2}$входы. Конечным результатом является то, что мы находим удовлетворительное назначение$C'$ тогда и только тогда $C$выполнимо. Время работы$\tilde{O}(2^{(n/2)(2-\epsilon)}\cdot |C|^{2-\epsilon}) = \tilde{O}(2^{n(1-\epsilon/2)}\cdot \textrm{poly}(|C|))$,