Завершена ли проблема поиска операторов для удовлетворения списка булевых переменных NP?

Это похоже на SAT, за исключением того, что мы знаем назначение каждой переменной, но не знаем назначения какого-либо логического оператора. В таком случае, является ли поиск присваивания каждого оператора таким образом, чтобы выражение оценило данное логическое значение как проблему NPC?

На самом деле, мне было интересно, если поиск назначения арифметических операторов для удовлетворения целочисленного арифметического выражения (например, $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$ = 10) является NP завершенным?

Я думаю , что с сложением и вычитанием проблема с разделами , которая является NP-сложной, сводится к вашей второй проблеме.

Учитывая множество мы создаем задачу$S = \{s_1, s_2, \ldots, s_n\}$

o p 1 s 2 o p 2 s 3 o p 3 … o p n - 1 s n = 0 . $s_1$ $op_1$ $s_2$ $op_2$ $s_3$ $op_3$ $\ldots op_{n-1}$ $s_n = 0$

Если решение существует, мы создаем два набора:

$S_1 = \{s_1\}\cup \{s_i | op_{i-1} = +\}$

$S_2 = \{s_i | op_{i-1} = -\}$

Эти два набора должны иметь одинаковую сумму при установке нашей исходной задачи, поэтому проблема разбиения решена. Это показывает, что не только сложно найти реальное решение этой проблемы, но и на самом деле трудно определить, существует ли решение (по крайней мере, для сложения и вычитания).

Для набора операций, который не позволяет создавать отрицательные целые числа, например, умножение и сложение, это не так ясно. Кроме того, это только показывает, что проблема слабо NP-трудна; может быть сокращение, которое дает более сильный результат, чем этот.

Краткий ответ. Операторская версия SAT эффективно разрешима - по крайней мере, если мы примем произвольные схемы двухвходных вентилей без разветвления, при любом желаемом выборе стробирования.

Длинный ответ Я предполагаю следующую форму логической проблемы:

$x \in \{0,1\}^n$$n \geqslant 2$$\mathcal G$$C$$\mathcal G$ $x$$x$$x$$C$

В частности, мы не навязываем конкретную структуру схемам (кроме двоичных деревьев), не допускаем разветвления (так что каждый бит используется только один раз), и вентили могут быть асимметричными. Допуская только двухбитные вентили, я исключаю вентиль NOT (но который может быть смоделирован наличием множества вентилей, которые связаны друг с другом отрицаниями, такими как AND / NAND ; также я исключаю вентили, которые просто выводят константы без входов , так что число вентилей в схеме фактически всегда будет для битного входа. Для краткости ниже я буду называть 2-TREE-OPSAT просто OPSAT$C$$x$$n-1$$n$; хотя анализ проблемы может стать намного более сложным для схем, допускающих произвольные k- входные вентили ( k-TREE-OPSAT ) или допускающих разветвление (которое мы могли бы назвать k-FANOUT-OPSAT ).

[ Отредактировано, чтобы добавить : мы можем легко адаптировать это, чтобы рассмотреть более общую проблему текущей ревизии вашего вопроса, в которой мы пытаемся отобразить данный к целевому значению , поменяв ролями и в приведенном ниже анализе; это приводит к смене ролей AND и OR , NAND и NOR и т. д. ] $x \in \{0,1\}^\ast$$b \in \{0,1\}$$0$$1$$\def\et{\wedge}\def\ou{\vee}\def\AND{\mathop{\text{AND}}}\def\NAND{\mathop{\text{NAND}}}\def\OR{\mathop{\text{OR}}}\def\NOR{\mathop{\text{NOR}}}\def\EQUAL{\mathop{\text{EQUAL}}}\def\PARITY{\mathop{\text{PARITY}}}$

Для фиксированного выбора проблема выбора подходящего дерева с подходящими воротами не отличается от логической дизъюнкции: использование эквивалентностей, таких как мы можем выполнять сокращения между коллекциями, связывающими более сложные наборы ворот с простыми (и мощными) наборами ворот; a может говорить о том, что один набор гейтов может эмулировать другие вентили, не принадлежащие этому набору, мудро выбирая некоторый элемент который имеет тот же эффект (когда представлен с определенным входом), что и вентиль , В частности, определенные комбинации вентилей (такие как ) могут моделировать постоянную функцию, дающую$x \in \{0,1\}^n$

Далее мы рассмотрим наборы затворов, включающие в себя различные типы затворов , а затем исключим эти затворы из более поздних случаев анализа, чтобы показать, что наборы затворов, включающие какой-либо один из затворов, приводят к решаемой проблеме. Мы будем исходить в порядке числа двух битовых строк , которые удовлетворяют ворота в вопросе, начиная с постоянной ворот до постоянной ворот.$G$$1$$0$

1. Для любого набора логических элементов который содержит постоянные вентили , мы можем просто построить схему используя только эти вентили, и в этом случае принимает любой .$\mathcal G$$G(x,y) = 1$$C$$C$$x$

2. ИЛИ и НАНД. Для любого набора вентилей который содержит : если все другие вентили удовлетворяют , то нет никакого выбора для выбора других вентилей, кроме в построении схемы . Схема только ворот принимает любую строку кроме . В противном случае существует элемент такой что тавтологичен. Таким образом, любой экземпляр OPSAT с легко; и подобные замечания относятся к .$\mathcal G$$\OR$$G \in \mathcal G$$G(x,y) \implies \OR(x,y)$$\OR$$C$$\OR$$x \in 0^\ast$$G \in \mathcal G$$\{G, \OR\}$$\OR \in \mathcal G$$\NAND \in \mathcal G$

3. Имплицитные ворота. Рассмотрим вентиль , который выводит ноль только в том случае, если . Для дальнейшего аналогичного анализа будет применяться для ворот . Рассмотрим любую строку . Если заканчивается на , разложить на подстроки вида ; к каждому такому мы рекурсивно применяем справа налево, что дает вывод для каждого . (Для подстроки длиной 1 мы используем тривиальную схему, т.е. оставляем этот вход в покое.) Аналогично, если$G(x,y) = \neg x \ou y$$(x,y) = (1,0)$$G'(x,y) = x \ou \neg y$
   
   $x \in \{0,1\}^n$$x$$0$$x$$w_j = 1^\ast 0$$w_j$$G$$0$$w_j$$x$ заканчивается на , разлагает на подстроки вида и рекурсивно применяет слева направо к каждому , что дает выход для каждого . Таким образом, мы можем свести задачу к построению цепей, которые удовлетворяются либо на либо на , где - это число подстрок или . Для мы можем согласиться с использованием gates, рекурсивно применяя слева направо. Это просто оставляет дело$1$$x$$w_j =0^\ast 1$$G$$w_j$$1$$w_j$$0^m$$1^m$$m$$1^\ast0$$0^\ast 1$$m \geqslant 2$$G$$G$$m = 1$ , для которого проблемным случаем являются входы . При любая схема, состоящая только из элементов, будет давать только более короткие строки вида , что в конечном итоге приведет к однобитовой строке : так что ни одна схема элементов не может быть удовлетворена этот вход. Если есть также ворота для которых , то тавтологично; или, если есть вентиль для которого , мы можем уменьшить строки вида$x \in 1^\ast 0$
   
   $x= 1^\ast 0$$G$$1^\ast 0$$0$$G$$H \in \mathcal G$$H(1,0) = 1$$\{G,H\}$$H \in \mathcal G$$H(1,1) = 0$$11^\ast 0$в строки вида , применяя к первым двум битам . В противном случае не может быть построена схема, которая принимает . Таким образом, для любого набора гейтов который содержит импликатообразные ворота, OPSAT прост.$(1^\ast 0)^\ast$$H$$x$$x \in 1^\ast 0$
   
   $\mathcal G$

4. Отрицания проекций. Рассмотрим ворота и . Мы рассматриваем , анализ с аналогичен. Сам по себе может принять любую строку в для , уменьшив последние бит до одного бита, а затем применив ; и он может аналогичным образом принять для , уменьшив последние бита до одного бита, а затем применив схему$\neg \pi_1(x,y) = \neg x$$\neg \pi_2(x,y) = \neg y$$\neg \pi_1$$\neg \pi_2$$\neg \pi_1$$0(0|1)^{n-1}$$n \geqslant 2$$n-1$$\neg \pi_1$$1(0|1)^{n-1}$$n \geqslant 3$$n-2$$\neg \pi_1(\neg \pi_1(x_1, x_2),x_3)$, Единственные входы, которые не могут принять схемы - это или ; Определение того, принимают ли они какие-либо дополнительные врата, тривиально. Таким образом, ОПСАТ легок для отрицания прогнозов.$\neg \pi_1$$10$$11$

5. ПАРИТЕТ и РАВЕНСТВО . Рассмотрим ворота . Очевидно, что множество ворот может быть точно удовлетворено только строками с нечетным числом 1s; мы рассматриваем преимущества добавления любых других ворот.$\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$$\mathcal G = \{\PARITY\}$$x \in \{0,1\}^n$

   • Любой набор который содержит как и или может моделировать схемы, которые содержат вентили или (соответственно) для фиксированных входов, которые Легкие случаи ОПСАТ .$\PARITY$$\AND$$\NOR(x,y) = \neg(x \ou y)$$\OR$$\NAND$
   • Либо либо можно использовать для имитации либо либо на двухбитовых подстроках четной четности, так что мы можем уменьшить наборы шлюзов с помощью этих ворота и к предыдущему случаю.$\pi_1(x,y) = x$$\pi_2(x,y) = y$$\AND$$\NOR$$\PARITY$
   • $\PARITY$ вместе с тавтологичны.$\EQUAL = \neg \PARITY$
   • Если мы к , мы можем принять любую строку четной четности, кроме , применив к -substring из , а затем применяя схему к остальным. Аналогично, вместе с может принимать любую строку, кроме строки вида . Дополнение как и позволяет нам строить схемы, которые принимают все входы, кроме и$\PARITY$$G_{01} = \neg x \et y$$x \in (11)^\ast 0^\ast$$G_{01}$$01$$x$$\PARITY$$\PARITY$$G_{10} = x \et \neg y$$x \in 0^\ast (11)^\ast$$\PARITY$$G_{01}$$G_{10}$$x \in 0^\ast$$x = 11$ .
   • Наконец, если мы константой gate , мы можем принять любой вход, кроме или , применяя gate к подстрока или , сокращающая до нечетного случая четности.$\PARITY$$Z(x,y) = 0$$x \in (11)^\ast$$x \in 0^\ast$$G$$01$$10$

   Таким образом, OPSAT легко для любого содержащего . Аналогичный анализ применяется для логического элемента как для логического элемента : потому что , схемы из ворота существенно подсчитывают четность числа сек на входе. Затем мы можем свести анализ для к анализу путем замены и .$\mathcal G$$\PARITY$
   
   $\EQUAL$$\PARITY$$\EQUAL(x,y) = \neg \PARITY(x,y) = \neg \PARITY(\neg x, \neg y)$$\EQUAL$$0$$\EQUAL$$\PARITY$$0$$1$

6. Проекционные ворота. Ворота и , взятые сами по себе, могут создавать только схемы, которые принимают строки, начинающиеся или заканчивающиеся на соответственно. Рассмотрим эффект увеличения шлюза любым другим вентилем (аналогичный анализ выполняется для ):$\pi_1(x,y) = x$$\pi_2(x,y) = y$$1$$\pi_1$$\pi_2$

   • Разрешение и и позволяет создать схему "выбора", которая просто выводит любой отдельный бит со входа; они могут принимать любые и дополнять их любым вентилем для которого позволяет построить удовлетворенную схему для любого .$\pi_1$$\pi_2$$x \ne 0^n$$G$$G(0,0) = 1$$x$
   • Если мы либо либо , мы можем смоделировать либо либо имплицитный логический элемент для фиксированных входов; ОПСАТ решен для обоих этих случаев.$\pi_1$$\NOR$$G_{01} = \neg x \et y$$\OR$
   • Если мы дополняем либо , , постоянными вентилями , либо любой их комбинацией, мы не получаем никакой дополнительной принимающей силы, так что мы все еще может принимать только строки, начинающиеся с .$\pi_1$$\AND$$G_{10} = x \et \neg y$$Z(x,y) = 0$$1$

   Таким образом, для любого другого гейта, который мы можем дополнить (или ), мы получим либо тавтологичный набор, не получим никакой дополнительной принимающей способности по сравнению с (или ), либо можем уменьшить до более раннего простого случая OPSAT , Тогда любой экземпляр OPSAT с или легко.$\pi_1$$\pi_2$$\pi_1$$\pi_2$$\pi_1 \in \mathcal G$$\pi_2 \in \mathcal G$

7. Дельта-функция ворот. Рассмотрим двухбитные вентили, для которых имеется только один вход, удовлетворяющий им: , , и . Схемы, выполненные только с воротами могут принимать только строку : добавление к ним любых других шлюзов дельта-функций позволяет имитировать либо , , либо , что является решаемыми случаями; аналогичные замечания относятся к . Кроме того, набор может также использоваться для имитации$\AND$$\NOR$$G_{10}(x,y) = x \et \neg y$$G_{01}(x,y) = \neg x \et y$$\AND$$1^\ast$$\EQUAL$$\pi_1$$\pi_2$$\NOR$$\{G_{01}, G_{10}\}$$\PARITY$Ворота. Таким образом, можно либо сосредоточиться на ворота или , возможно , с добавлением затвора . Мы фокусируемся на , причем случай аналогичен. Схемы, сделанные только из могут быть построены так, чтобы принимать , за исключением строки , путем применения произвольной схемы к последним битам и затем применения схемы . Ясно, что строка не может быть принята или ; и мы можем показать по индукции, что любой$G_{10}$$G_{01}$$Z(x,y) = 0$$G_{10}$$G_{01}$
   
   $G_{10}$$1(0|1)^{n-1}$$11$$n-2$$G_{10}(x_1, G_{10}(x_2, x_3))$$11$$G_{10}$$Z$$G_{10}$Схема, которая принимает строку, должна иметь промежуточные результаты от логических элементов в самой левой ветви, дающих , до самого левого входа. Дополнительное преимущество не достигается при добавлении ворот. Следовательно, схемы могут принимать только .$1$$Z$$G_{10}$$x \in 1(0|10|11)(0|1)^\ast$

8. Наконец, цепи, состоящие только из вентилей, не принимают входные данные.$Z$

Поскольку каждый ворота приводит к четко определенному и в целом довольно большому классу входов , которые он принимает, с дополнительными воротами , стремящихся к банальным проблемам, мы находим , что 2-ДЕРЕВО-OPSAT в P .