Złożoność konwersji obwodu boolowskiego na wzór boolowski

Biorąc pod uwagę obwód logiczny na zmiennych (który używa tylko bramek NOT, AND i OR), jaki jest najbardziej skuteczny sposób na wyodrębnienie wzoru logicznego reprezentowanego przez obwód? Czy istnieje algorytm polimeime dla tego problemu? $C$ $n$

cc.complexity-theory time-complexity boolean-functions

— Nikhil
źródło

jaki rodzaj bram ma obwód?

— Lew Reyzin

Jakie ograniczenia dotyczące włączania i wyłączania wentylatora? Jeśli jest to tylko pojedyncze rozwinięcie, to jest banalne: sam obwód jest w zasadzie AST dla tej formuły.

— Mark Reitblatt,

Ograniczony wachlarz, aby być ogólnym. Mówiąc dokładniej, powiedzmy, że AND i OR mają fan-in 2. W wielu źródłach literatury stwierdzam, że obwód i formuły są używane zamiennie, ale chcę wiedzieć, czy przekształcenie obwodu w formułę jest łatwe problem.

— Nikhil

Zasadniczo można oczekiwać, że każda równoważna formuła może mieć wykładniczy rozmiar nawet w przypadku małego obwodu.

— Kristoffer Arnsfelt Hansen

Wielomianowe formuły wielkości są równoważne obwodom . Obwody polisize ( ) nie są znane jako równoważne . Wzory i obwody stosuje się zamiennie, zwykle gdy głębokość obwodu jest ograniczona.

N C^{1}

$NC^1$

P / p o l y

$P/poly$

N C^{1}

$NC^1$

— Kaveh

Jeśli dobrze rozumiem twoje pytanie, powiedziałbym, że możesz użyć standardowej redukcji z CIRCUIT-SAT do SAT: Reprezentuj każdą bramkę jako nową zmienną, a następnie reprezentuj cały obwód w postaci CNF, przy czym każda klauzula ma postać , gdzie jest nową zmienną, a wzór dla bramki podaje , używając zmiennych dla innych bramek do reprezentowania danych wejściowych. Można tego dokonać przez proste przejście (w czasie liniowym, co jest wyraźnie optymalne). $(v\leftrightarrow\phi)$ $v$ $\phi$

Na przykład, jeśli masz trzy wejścia, , i , z bramkami AND łączącymi i a także i oraz bramką OR łączącą ich wyjścia, możesz wprowadzić trzy zmienne reprezentujące bramki - , i - i przepisujemy formułę naZauważ, że zmienna wyjściowa jest dołączona jawnie. $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\,.$

Wprowadzenie do algorytmów Cormena i in. wyjaśnia to szczegółowo w rozdziale o kompletności NP.

— Magnus Lie Hetland
źródło

Czy CIRCUIT-SAT nie korzysta z fan-out 1 bramek?

— Mark Reitblatt

Jasne - ale o ile widzę, nie wpływa to na redukcję / transformację. Pomysł przedstawienia każdego wyjścia jako nowej zmiennej oznacza, że możesz użyć każdego wyjścia kilka razy (co odpowiada dowolnie dużemu rozkładowi). Innymi słowy, rozwiązanie podane w tej odpowiedzi powinno działać dla dowolnych obwodów.

— Magnus Lie Hetland

Domyślam się, że nie o to proszono. Myślę, że potrzebne jest stworzenie formuły na tym samym zestawie zmiennych, co obwód.

— Kristoffer Arnsfelt Hansen

Hm Tak, prawdopodobnie masz rację. Wprowadzenie nowych zmiennych ma sens w przypadku CIRCUIT-SAT do CNF-SAT, ale nie w bardziej ogólnym ustawieniu - zgadzam się.

— Magnus Lie Hetland

@Kristoffer: Miałem dokładnie na myśli to, co powiedziałeś. Biorąc pod uwagę obwód na Chcę, aby formuła była dokładnym wyrażeniem logicznym dla obwodu.

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)$

— Nikhil