Kompleksitas mengubah sirkuit boolean ke formula boolean

Diberikan sirkuit boolean pada variabel (yang menggunakan gerbang NOT, AND dan OR), apa cara paling efisien untuk mengekstrak rumus boolean yang diwakili oleh sirkuit? Apakah ada algoritma polytime untuk masalah ini? $C$ $n$

cc.complexity-theory time-complexity boolean-functions Nikhil
sumber

apa jenis gerbang yang dimiliki sirkuit?

Lev Reyzin

Apa batasan fan-in atau fan-out? Jika hanya fan-out tunggal maka itu sepele: sirkuit itu sendiri pada dasarnya adalah AST untuk formula.

Mark Reitblatt

Penggemar terikat untuk menjadi umum. Tetapi lebih tepatnya, katakanlah AND dan ATAU memiliki fan-in 2. Dalam banyak referensi dalam literatur, saya menemukan bahwa rangkaian dan rumus digunakan secara bergantian, tetapi saya ingin tahu apakah mengubah sirkuit ke rumus adalah hal yang mudah. masalah.

Nikhil

Secara umum Anda akan mengharapkan bahwa rumus yang setara dapat berukuran eksponensial bahkan untuk sirkuit kecil.

Kristoffer Arnsfelt Hansen

Rumus ukuran polinomial setara dengan sirkuit

. Sirkuit polysize (

) tidak diketahui setara dengan

. Rumus dan sirkuit digunakan secara bergantian biasanya ketika kedalaman sirkuit dibatasi.

N C^{1}

$NC^1$

P / p o l y

$P/poly$

N C^{1}

$NC^1$

Kaveh

Jawaban:

$(v\leftrightarrow\phi)$ $v$ $\phi$

$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\,.$

Pengantar Algoritma oleh Cormen et al. menjelaskan ini secara rinci, dalam bab tentang NP-Completeness.

Magnus Lie Hetland
sumber

Tidakkah CIRCUIT-SAT menggunakan gerbang keluar 1?

Mark Reitblatt

Tentu — tapi sejauh yang saya bisa lihat, itu tidak mempengaruhi pengurangan / transformasi. Gagasan untuk mewakili setiap output sebagai variabel baru berarti bahwa Anda dapat menggunakan kembali setiap output sebagai input beberapa kali (sesuai dengan fan-out besar yang sewenang-wenang). Dengan kata lain, solusi yang diberikan dalam jawaban ini harus bekerja untuk rangkaian arbitrer.

Magnus Lie Hetland

Dugaan saya adalah bahwa ini bukan yang diminta. Saya pikir yang diinginkan adalah membuat formula pada rangkaian variabel yang sama dengan rangkaian.

Kristoffer Arnsfelt Hansen

Hm Ya, Anda mungkin benar. Memperkenalkan variabel baru masuk akal dalam kasus CIRCUIT-SAT ke CNF-SAT, tetapi tidak dalam pengaturan yang lebih umum — saya setuju.

Magnus Lie Hetland

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