关于布尔电路的一些笔记

布尔电路(Boolean Circuit),是计算复杂度理论中的一个重要模型。但是好像这方面的中文资料很少。我把我学到的做一点笔记写在这里吧。不是教学向文章,但是可能能让你理解一些这方面的内容。

什么是布尔电路?

布尔电路是“一些由导线连接的输入的集合。不能有环。门有三种:与,或,非”(Sipser, p. 380)。这是Sipser给出的比较简洁且抽象的一种定义。Arora和Barak给出的定义是“一个展示了如何通过输入和一系列的布尔操作(与,或,非)得到一个输出的一个程序图”(Arora & Barak, p. 107)。这两个定义虽然看起来差别挺大,但实际上确实描述了同一种东西。

实现了异或功能的布尔电路

布尔电路理论上可以帮助我们证明P≠NP。从上世纪70年代起,研究者们就试图证明电路下界。后面我们(可能)会讲到现在取得的成果以及目前面临的困难。

一般来说,定义上我们会要求每个与门和或门的入度(即输入的值的个数)为2。实际上我们可以很容易地用f-1个入度为2的与门实现f个输入的与门(或门也一样)。但是当我们考虑限制深度的电路时,就不能轻易地做这个替换。

这样定义有一个好处,就是布尔电路模型化了现代电子计算机使用的芯片(实际上现代的芯片里的电路是有环的,其用来实现内存,但我们仍然可以在\(O(CT)\)大小的布尔电路上执行有C个门的芯片在时间T内完成的任何计算)。

电路族和语言识别)如果\(T:\mathbb{N}\rightarrow\mathbb{N}\)是一个函数,一个\(T(n)\)大小的电路族是一系列布尔电路\(\{C_n\}_{n\in\mathbb{N}} \),每个\(C_n\)有\(n\)个输入和一个输出,且它的大小\(|C_n|\le T(n)\)。如果存在一个\(T(n)\)大小的电路族使得对于每个\(x\in\{0,1\}^n, x\in L\Leftrightarrow C_n(x)=1\),我们就说语言\(L\)是属于\(\mathbf{SIZE}(T(n))\)的。

(\(\mathbf{P_{/poly}}\)的定义) \(\mathbf{P_{/poly}}\) 是所有能被多项式大小的布尔电路所判定的语言的集合。即, \(\mathbf{P_{/poly}}=\cup_c\mathbf{SIZE}(n^c)\) 。

每个人都有可能会问:不给\(c\)设个上限吗?要个\(n^{100}\)的电路设计有啥用呢?首先,如果我们有一个\(n^{100}\)的设计方案,很大几率上我们可以减少它最高次项(正如计算复杂度那样,事实上我们好像很少听到高于\(n^4\)的多项式算法)。其次,作为理论计算机科学家们,他们当然希望证明SAT是不在 \(\mathbf{P_{/poly}}\) 里面的。如果我们允许\(n^{100}\)大小的电路存在,这个结果只会变得更有力。

定理:\(\mathbf{P}\subseteq \mathbf{P_{/poly}} \)。证明很长,我就不在这里写了。大概就是对于一个执行时间为\(t(n)\)的图灵机,画一个\(t(n)\times t(n)\)的画面(像证明SAT是NP-complete的时候一样),然后用一个大的布尔电路去模拟这个图灵机。这样每个执行时间为\(O(t(n)) \)的图灵机都能被\(O(t^2(n))\)大小的布尔电路模拟。

定义:(电路可满足性问题)语言CKT-SAT是所有能被满足的(字符串表示的)电路的集合。即,一个字符串表示的\(n\)个输入的电路\(C\)是属于CKT-SAT的当且仅当存在\(u\in\{0,1\}^n\)使得\(C(u)=1\)。CKT-SAT是NP完全的。

引理CKT-SAT\(\le_p\)3SAT。证明:假设我们有个电路\(C\),我们要把它映射到一个3CNF式子\(\phi\)上。对于每个\(C\)里面的结点\(v_i\),我们都在\(\phi\)中有一个对应的变量\(z_i\)。如果\(v_i\)是两个结点\(v_j\)和\(v_k\)的与,那么我们就在\(\phi\)中添加跟条件\(z_i=(z_j\wedge z_k)\)等价的语句,即:\[(\bar{z}_i\vee\bar{z}_j\vee z_k)\wedge (\bar{z}_i\vee {z}_j\vee \bar{z}_k)\wedge (\bar{z}_i\vee {z}_j\vee z_k) \wedge ({z}_i\vee\bar{z}_j\vee \bar{z}_k) \]对于或和非操作也类似。最后如果\(v_i\)是输出结点,那么就把\((z_i)\)作为一个语句添加进\(\phi\)。这样一来,\(\phi\)是可满足的当且仅当\(C\)是可满足的。

发表评论

电子邮件地址不会被公开。

*