Наименьшая логическая схема для генерации языка

Рассмотрим непустой язык двоичных строк длины . Я могу описать булевой схемой с входами и одним выходом, так что истинно тогда и только тогда, когда : это хорошо известно.$L$$n$$L$$C$$n$$C(w)$$w \in L$

Тем не менее, я хочу представлять с булевой схемой с выходами и определенным количеством входов, скажу , таким образом, что множество выходных значений для каждого из возможных входов точно .$L$$C'$$n$ $m$$C'$$2^m$$L$

Учитывая , как я могу найти такую ​​схему минимального размера, и какова сложность? Существует ли какая-либо связь между известными границами размера цепей первого рода ( ) и цепями второго рода ( ) или сложностью их нахождения?$L$$C'$$C$$C'$

(Заметьте, что существует некоторая двойственность в следующем смысле: учитывая , я легко могу решить, находится ли входное слово в , оценивая схему, но в общем случае NP-сложно найти какое-то слово в$C$$w$$L$$L$ , найдя присваивание такое, что вывод является истинным. Учитывая$C'$ NP также трудно определить, находится ли какое-то входное слово$w$ в$L$ потому что я должен видеть, дает ли присваивание$w$ качестве вывода, но легко найти какое-то слово в$L$ путем оценки схемы на любом произвольном входе.)

Я укажу на простую связь с недетерминированными схемами и кратко прокомментирую криптографическую стойкость.

Для определите сложность изображения, обозначенную i m c ( S ) , как минимальное число вентилей в любой булевой схеме C (fanin-two, AND / OR / NOT) C : { 0 , 1 } м → { 0 , 1 } п , образ которого S . Вопрос спрашивает о сложности вычислений i m c ( S ) , учитывая представление таблицы истинности $S \subseteq \{0, 1\}^n$$imc(S)$$C: \{0, 1\}^m \rightarrow \{0, 1\}^n$$S$$imc(S)$$S$(строка длиной ).$2^n$

Также определяют недетерминированную сложность схемы из , который мы будем обозначать п с гр ( S ) , как наименьшее недетерминированной цепи C ( х , у ) : { 0 , 1 } п + т ' → { 0 , 1 } принимает точно S . То есть мы требуем от C, что x ∈ S тогда и только тогда, когда ∃ y : C ( $S$$ncc(S)$$C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$$S$$C$$x \in S$ . Это стандартное понятие, используемое для определения неоднородного класса N P / p o l y : это класс всех множеств S = { S n } n > 0 с S n ⊆ { 0 , 1 } n , такой, что n c c ( S n ) ≤ p o l y ( n ) .$\exists y: C(x, y) = 1$$NP/poly$$S = \{S_n\}_{n > 0}$$S_n \subseteq \{0, 1\}^n$$ncc(S_n) \leq poly(n)$

Я хотел бы отметить, что . Оба направления этого неравенства легко проверить. $imc(S) = ncc(S) \pm O(n)$

Пусть обозначает детерминированную сложность схемы. Используя Разборова-Рудича, статья, о которой упоминает Дай Ле, показывает (грубо говоря), что при определенных криптографических предположениях трудно в вычислительном отношении отличить таблицы истинности S с малым d c c ( S ) от таблиц истинности действительно случайных S (с d c c ( S ) почти максимальным). Случайные S также имеют n c c ( S ) почти максимальную, и мы, конечно, имеем$dcc(S)$$S$$dcc(S)$$S$$dcc(S)$$S$$ncc(S)$ . Так что ваша проблема сложна при тех же предположениях.$ncc(f) \leq dcc(f)$

Что сложнее вычислить, учитывая таблицу истинности для , d c c ( S ) или n c c ( S ) ? Есть ли сокращение в любом случае? Я не знаю.$S$$dcc(S)$$ncc(S)$

Вы должны взглянуть на эту статью Кабанец и Цай. Я процитирую реферат статьи:

Мы изучаем сложность задачи минимизации схемы: учитывая таблицу истинности булевой функции и параметр s , решаем, можно ли реализовать f с помощью булевой схемы размером не более s . Мы спорим, почему эта проблема вряд ли может быть в P (или даже в P / p o l y ), приводя ряд удивительных последствий такого предположения. Мы также утверждаем, что доказательство того, что эта проблема является N P -завершенной (если это действительно так), подразумевало бы доказательство сильных схем нижних границ для класса E , что выходит за рамки известных в настоящее время методов.$f$$s$$f$$s$$\mathsf{P}$$\mathsf{P}/\mathsf{poly}$$\mathsf{NP}$$\mathsf{E}$

Хотя схема вы упомянули, вычисляет функцию F : { 0 , 1 } m → L , мы можем думать о ней как о последовательности схем C ′ 1 , C ′ 2 , … , C ′ n , где C ′ i вычисляет я т ч выходной бит F . Поскольку каждый C ' i вычисляет булеву функцию { 0 , 1 } $C'$$F:\{0,1\}^m \rightarrow L$$C'_1,C'_2,\ldots,C'_n$$C'_i$$i^{\rm th}$$F$$C'_i$ , минимизация цепей C ′ i кажется сложной в соответствии с приведенным выше результатом.$\{0,1\}^m\rightarrow \{0,1\}$$C'_i$