Сложность преобразования булевой схемы в булеву формулу

Учитывая булеву схему для переменных (которая использует только вентили NOT, AND и OR), каков наиболее эффективный способ извлечь логическую формулу, представленную схемой? Есть ли алгоритм Polytime для этой проблемы? $C$ $n$

cc.complexity-theory time-complexity boolean-functions Нихилу
источник

какие ворота есть в схеме?

Лев Рейзин

Какие ограничения на разветвление или разветвление? Если это просто разветвление, то это тривиально: сама схема является AST для формулы.

Марк Рейтблатт

Ограниченный фан-ин, чтобы быть общим. Но если быть точным, допустим, что AND и OR имеют веер 2. Во многих ссылках в литературе я считаю, что схемы и формулы используются взаимозаменяемо, но я хочу знать, является ли преобразование схемы в формулу простым проблема.

Нихил

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

Кристоффер Арнсфельт Хансен

Полиномиальные формулы размеров эквивалентны

цепям . Polysize схемы (

) не знают, что эквивалентно

. Формулы и схемы используются взаимозаменяемо обычно, когда глубина схемы ограничена.

N C^{1}

$NC^1$

P / p o l y

$P/poly$

N C^{1}

$NC^1$

Каве

Если я правильно понимаю ваш вопрос, я бы сказал, что вы можете использовать стандартное сокращение от CIRCUIT-SAT до SAT: представлять каждый вентиль как новую переменную, а затем представлять всю схему в форме CNF, причем каждое предложение имеет форму , где - новая переменная, а формула для ворот задается как , используя переменные для других вентилей для представления входных данных. Это можно сделать простым обходом (за линейное время, которое явно оптимально). $(v\leftrightarrow\phi)$ $v$ $\phi$

Например, если у вас есть три входа, , и , с вентилями AND, связывающими и а также и , и вентилем OR, связывающим их выходы, вы можете ввести три переменные представить ворота - , и соответственно - и переписать формулу в $x_1$ $x_2$ $x_3$ $x_1$ $x_2$ $x_2$ $x_3$ $v_1$ $v_2$ $v_3$ Обратите внимание, что выходная переменная включена явно.

(v_{1} \leftrightarrow (x_{1} \land x_{2})) \land (v_{2} \leftrightarrow (x_{2} \land x_{3})) \land (v_{3} \leftrightarrow (v_{1} \lor v_{2})) \land v_{3} .

$(v_1\leftrightarrow(x_1\land x_2))\land (v_2\leftrightarrow(x_2\land x_3))\land (v_3\leftrightarrow(v_1\lor v_2))\land v_3\,.$

Введение в алгоритмы Cormen et al. объясняет это подробно, в главе о NP-полноте.

Магнус Ли Хетланд
источник

Разве CIRCUIT-SAT не использует вентиляционные отверстия 1?

Марк Рейтблатт

Конечно, но, насколько я вижу, это не влияет на уменьшение / преобразование. Идея представления каждого выхода в качестве новой переменной означает, что вы можете повторно использовать каждый выход в качестве входа несколько раз (что соответствует произвольно большому разветвлению). Другими словами, решение, данное в этом ответе, должно работать для произвольных цепей.

Магнус Ли Хетланд

Я думаю, что это не то, что просят. Я думаю, что нужно сделать формулу для того же набора переменных, что и схема.

Кристоффер Арнсфельт Хансен

Гектометр Да, вы, вероятно, правы. Введение новых переменных имеет смысл в случае CIRCUIT-SAT для CNF-SAT, но не в более общей ситуации - я согласен.

Магнус Ли Хетланд

C

$C$

x_{1}, x_{2}, \dots, x_{n}

$x_1, x_2, \ldots, x_n$

ϕ (x_{1}, x_{2}, \dots, x_{n})

$\phi(x_1, x_2, \ldots, x_n)$

Сложность преобразования булевой схемы в булеву формулу

Ответы: