經(jīng)典計(jì)算：Lecture2 Boolean Circuits I

2 Boolean circuits

2.1 Definitions. Complete bases

Boolean value: 0和1妒茬，ture or false
Boolean circuit：把一個(gè)給定的Boolean function表示成其他Boolean functions的組合，Boolean circuit是對上述過程的表示。
Boolean functioon： $n$ 個(gè)變量 $F:\mathbb{B}^n \rightarrow \mathbb{B}$
basis：由Boolean functions組成的固定集合 $A$ 辐宾。在 $A$ 里的function會有不同數(shù)量的參數(shù)(different arity)沈条。

circuit components: 一個(gè)在 $A$ 上的circuit $C$ 是一系列assifgnments:
$n$ 個(gè)輸入的變量 $x_1, x_2, ...., x_n$
一些輔助(auxiliary)變量 $y_1, y_2, ..., y_m$ 我磁。
第 $j$ 個(gè)賦值形如 $y_j =f_j(u_1, ...,u_r)$ ,其中 $f_j$ 是 $A$ 中的function古拴， $u_i$ 是輸入變量或者是 $y_j$ 之前的輔助變量。

最后一個(gè)輔助變量 $y_m$ 就是計(jì)算的result钱骂。有 $n$ 個(gè)輸入的boolean citrcuit計(jì)算了一個(gè)boolean function $F:\mathbb{B}^n \rightarrow \mathbb{B}$ 叔锐，如果對任意輸入 $x_1, x_2, ...,x_n$ ，都有 $y_m=F(x_1, x_2, ...,x_n)$ 见秽。

在circuit中選擇 $m$ 個(gè)輔助比特作為輸出時(shí)愉烙，就可以定義由circuit計(jì)算多個(gè)輸出的函數(shù) $F:\mathbb{B}^n \rightarrow \mathbb{B}^m$ 。

電路也可以用無環(huán)有向圖(Acyclic directed graph)表示解取。

Boolean circuits

其中最頂端in-degree是0的頂點(diǎn)代表輸入齿梁；
其他頂點(diǎn)代表從basis中選出來的function，in-degree代表了輸入這個(gè)函數(shù)的變量個(gè)數(shù)肮蛹，match the arity of the function;
每一條進(jìn)入頂點(diǎn)的邊勺择，都代表了一個(gè)變量的輸入；
最下面的是輸出頂點(diǎn)伦忠。
graph = assignments省核。二者可以互相轉(zhuǎn)化。

Formula: 除了最后一個(gè)作為輸出的輔助變量之外昆码，其他的輔助變量都只用了一次气忠。但是輸入變量可以多次使用邻储。Formula的graph可以用樹來表示，葉子結(jié)點(diǎn)是輸入旧噪，一個(gè)輸入會出現(xiàn)多次吨娜。我們可以把一個(gè)formula表示成只有輸入， $A$ 中的function和括號的表達(dá)式淘钟，且它的長度和assignments的長度差不多宦赠。如果是一般的boolean function，則長度可能會指數(shù)增長米母。

Complete basis: 基 $A$ 被稱作完備的勾扭，如果任意boolean function $f$ ，都存在基 $A$ 上的circuit可以計(jì)算 $f$ 铁瞒。

最常見的basis包含如下三種操作(negation, disjunction, conjunction):
$NOT(x) = \neg x, OR(x_1, x_2)=x_1 \vee x_2, AND(x_1, x_2) = x_1 \land x_2$

定理2.1 The basis {NOT, OR, AND} = { $\neg, \vee, \land$ } is complete.

proof:假設(shè)function取值為1的自變量只有一種妙色，則它可以由literals的conjunction來計(jì)算；literals是 $x$ 或者 $\neg x$ 慧耍。例如 $f(x_1, x_2, x_3)$ 當(dāng) $x_1=1, x_2=0, x_3=1$ 時(shí)為真永品，則 $f(x_1, x_2, x_3)=x_1 \land \neg x_2 \land x_3.$
更一般的昌腰，一個(gè)函數(shù) $f$ 可以表達(dá)為如下形式： $f(x) = \vee_{\{u: f(u)=1\}}\chi_u(x),$ 其中 $u$ 時(shí)01串蟹腾；如果 $x=u$ 旁钧，則有 $\chi_u(x)=1$ ，否則為0师枣。 $\square$

DNF(disjunctive normal form): 是a disjunction of conjunctions of literals怪瓶。也就是 $f(x) = \vee_{\{u: f(u)=1\}}\chi_u(x)萧落。$

CNF(conjunctive normal form): 是a conjunction of disjunctions of literals践美。用De Morgan's identities 可以將上面DNF轉(zhuǎn)化為CNF。

根據(jù)identities找岖，basis{ $\neg, \vee, \land$ }是冗余的陨倡，只需要{ $\neg, \vee$ }或者{ $\neg, \land$ }就可以構(gòu)成完備基(complete bases). { $\land, \oplus$ }也是完備基。

Circuit complexity

size of circuit: 一個(gè)circuit中assignments的數(shù)量许布。
circuit complexity of $f$ : 在基 $A$ 上的計(jì)算函數(shù) $f$ 的circuit的最小(minimal) size兴革，記為 $c_A(f)$ 。
此處的復(fù)雜度 $c_A(f)$ 和基 $A$ 的選取有關(guān)蜜唾。但從一個(gè)有限基變換到另一個(gè)基杂曲，對復(fù)雜度的改變最多只是一個(gè)常數(shù)，所以有 $c_{A_1}(f) = O(c_{A_2}(f))$ 袁余。所以對基的選取并不是很重要擎勘，我們記 $c(f)$ 為circuit complexity of $f$ with respect to some finite comloete basis。

2.2 Circuits versus Turing machines.

對于一個(gè)predicate $F: \mathbb{B^*} \rightarrow \mathbb{B}$ 颖榜，可以固定他的輸入長度為 $n$ 棚饵，則我們可以得到如下的Boolean function: $F_n(x_1, x_2, \dots, x_n) = F(x_1, x_2, \dots, x_n).$ 從而煤裙，可以把predicate $F$ 看成是一列Boolean functions $F_0, F_1, ...$

類似的，partial function $F: \mathbb{B^*} \rightarrow \mathbb{B}^*$ 也可以看作一列partial functions $F_n: \mathbb{B}^n \rightarrow \mathbb{B}^{p(n)}$ 噪漾。為了簡單起見硼砰，后面的討論集中于predicates。

定義2.1 P/ploy(nonuniform P):

A predicate $F$ belongs to the class P/poly if $c(F_n)=\text{ploy}(n).$
此處的nonuniform欣硼，非均勻题翰，是說對不同的輸入長度，都有一個(gè)boolean circuit的size是多項(xiàng)式的分别。

定理2.2 $P \subset P/poly$ .

proof: 取 $F \in P$ 遍愿，證明 $F \in P/poly$ 。
對 $F$ 來說耘斩，存在圖靈機(jī) $M$ 沼填，runs in polynomial time and space。對 $n$ 長的輸入括授，step $T=poly(n)$ 坞笙，space $s=poly(n)$ ，所以可以拿一個(gè)space-time的圖表來表示荚虚。

space-time diagram

其中每一個(gè)cell $\Gamma_{j,k}$ 記錄了圖靈機(jī)在 $j$ step薛夜， $k$ -th cell的symbol和圖靈機(jī)的狀態(tài)。因?yàn)閟ymbol和狀態(tài)都是有限且與 $n$ 無關(guān)的版述，所以這些狀態(tài)可以編碼成二進(jìn)制串梯澜，長度與 $n$ 無關(guān)。由于每次head位移最多是1渴析，所以每一個(gè)cell只由上面相鄰三個(gè)決定晚伙。這個(gè)決定關(guān)系可以看作是一個(gè)boolean function，而且可以由circuit of size O(1)計(jì)算俭茧。把這些circuits組合起來形成一個(gè)大的circuit咆疗，把上面的space-time diagram算完，這個(gè)大的circuit的size是 $O(sT)O(1)=poly(n)$ 母债。
輸入部分需要 $O(n)$ assignment午磁，輸出部分只要看第一個(gè)cell就可以， $O(1)$
毡们。
總體來說迅皇，我們得到了一個(gè) $\text{poly}(n)$ -size的circuit計(jì)算了Boolean function $F_n$ 。

Remark2.1 $P \neq P/poly$ 衙熔，也就是說 $P$ 是 $P/poly$ 的真子集登颓。

舉例：設(shè) $\phi: \mathbb{N} \rightarrow \mathbb{B}$ 是任意函數(shù)。令predicate $F_\phi(x) = \phi(|x|)$ 青责。則 $(F_\phi(x))_n$ 是一個(gè)常數(shù)函數(shù)挺据， $c((F_\phi(x))_n)=O(1)$ 取具，所以 $F_\phi \in P/poly$ for any $\phi$ 。但對于noncomputable的函數(shù) $\phi$ 來說扁耐， $F_\phi$ 不可計(jì)算暇检，不屬于 $P$ 。

Remark2.2 $P/poly$ 是對 $P$ 很好的近似 for many purposes婉称。

事實(shí)上块仆，class $P/poly$ 相對來說很小：size為 $poly(n)$ 的circuit的數(shù)量不會超過 $O(((n+poly(n))^2)^{poly(n)}) = 2^{2poly(n)(log(poly(n))+O(1))} = 2^{poly(n)}.$ 而輸入長度為 $n$ 的Boolean function共有 $2^{2^n}$ 個(gè)王暗。uniform和nonuniform computation的不同對于更大的復(fù)雜性類中非常重要悔据。

EXPTIME: the class of predicates decidable in time $2^{ploy(n)}$ ，是一個(gè)非平凡的可計(jì)算類俗壹。然而科汗，把它類比到nonuniform之后，它就包含了所有的predicates.我們可以把所有的可能性編碼到指數(shù)線路中绷雏。

定理2.3 Alternative P Theorem:

Predicate $F \in P$ 當(dāng)且僅當(dāng) 如下條件成立：

$F \in P/poly$ ;
Boolean functions $F_n$ 由polynomial-size的circuits $C_n$ 計(jì)算時(shí)有如下性質(zhì)：存在一個(gè)圖靈機(jī)头滔，對每一個(gè)正整數(shù)輸入 $n$ (二進(jìn)制編碼，長度為 $\log(n)$ )涎显，運(yùn)行時(shí)間為 $poly(n)$ 并且構(gòu)建了circuit $C_n$ 坤检。

A 列滿足上面性質(zhì)的 $C_n$ 被稱為polynomial-time uniform。
證明：左推右由定理2.2證明過程是顯然的期吓。
右推左早歇，(不理解定理第二條里面圖靈機(jī)是干什么的)。

最后編輯于：2022.03.23 19:15:36

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末讨勤，一起剝皮案震驚了整個(gè)濱河市箭跳，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌悬襟，老刑警劉巖衅码，帶你破解...
沈念sama閱讀 221,695評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件拯刁，死亡現(xiàn)場離奇詭異脊岳，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)垛玻，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,569評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門割捅，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人帚桩，你說我怎么就攤上這事亿驾。” “怎么了账嚎？”我有些...
開封第一講書人閱讀 168,130評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵莫瞬，是天一觀的道長儡蔓。經(jīng)常有香客問我，道長疼邀，這世上最難降的妖魔是什么喂江？我笑而不...
開封第一講書人閱讀 59,648評論 1贊 297
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮旁振，結(jié)果婚禮上获询，老公的妹妹穿的比我還像新娘。我一直安慰自己拐袜，他們只是感情好吉嚣，可當(dāng)我...
茶點(diǎn)故事閱讀 68,655評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著蹬铺，像睡著了一般尝哆。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上甜攀，一...
開封第一講書人閱讀 52,268評論 1贊 309
城市分裂傳說
那天较解，我揣著相機(jī)與錄音，去河邊找鬼赴邻。笑死印衔，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的姥敛。我是一名探鬼主播奸焙，決...
沈念sama閱讀 40,835評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼彤敛！你這毒婦竟也來了与帆？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,740評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤墨榄，失蹤者是張志新（化名）和其女友劉穎玄糟，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體袄秩，經(jīng)...
沈念sama閱讀 46,286評論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡阵翎，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,375評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了之剧。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片郭卫。...
茶點(diǎn)故事閱讀 40,505評論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖背稼，靈堂內(nèi)的尸體忽然破棺而出贰军，到底是詐尸還是另有隱情，我是刑警寧澤蟹肘，帶...
沈念sama閱讀 36,185評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布词疼，位于F島的核電站俯树，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏贰盗。R本人自食惡果不足惜聘萨，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,873評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望童太。院中可真熱鬧米辐，春花似錦、人聲如沸书释。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,357評論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽爆惧。三九已至狸页，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間扯再，已是汗流浹背芍耘。一陣腳步聲響...
開封第一講書人閱讀 33,466評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留熄阻，地道東北人斋竞。一個(gè)月前我還...
沈念sama閱讀 48,921評論 3贊 376
代替公主和親
正文我出身青樓，卻偏偏與公主長得像秃殉，于是被迫代替她去往敵國和親坝初。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,515評論 2贊 359

經(jīng)典計(jì)算：Lecture2 Boolean Circuits I

2 Boolean circuits

2.1 Definitions. Complete bases

定理2.1 The basis {NOT, OR, AND} = {} is complete.

Circuit complexity

2.2 Circuits versus Turing machines.

定義2.1 P/ploy(nonuniform P):

定理2.2 .

Remark2.1 衙熔，也就是說是的真子集登颓。

Remark2.2 是對很好的近似 for many purposes婉称。

定理2.3 Alternative P Theorem:

推薦閱讀更多精彩內(nèi)容

定理2.1 The basis {NOT, OR, AND} = { $\neg, \vee, \land$ } is complete.

定理2.2 $P \subset P/poly$ .

Remark2.1 $P \neq P/poly$ 衙熔，也就是說 $P$ 是 $P/poly$ 的真子集登颓。

Remark2.2 $P/poly$ 是對 $P$ 很好的近似 for many purposes婉称。