经典计算：Lecture2 Boolean Circuits I

2022-03-18 本文已影响0人 richybai

2 Boolean circuits

2.1 Definitions. Complete bases

Boolean value: 0和1，ture or false
Boolean circuit：把一个给定的Boolean function表示成其他Boolean functions的组合，Boolean circuit是对上述过程的表示。
Boolean functioon： $n$ 个变量 $F:\mathbb{B}^n \rightarrow \mathbb{B}$
basis：由Boolean functions组成的固定集合 $A$ 。在 $A$ 里的function会有不同数量的参数(different arity)。

circuit components: 一个在 $A$ 上的circuit $C$ 是一系列assifgnments:
$n$ 个输入的变量 $x_1, x_2, ...., x_n$
一些辅助(auxiliary)变量 $y_1, y_2, ..., y_m$ 。
第 $j$ 个赋值形如 $y_j =f_j(u_1, ...,u_r)$ ,其中 $f_j$ 是 $A$ 中的function， $u_i$ 是输入变量或者是 $y_j$ 之前的辅助变量。

最后一个辅助变量 $y_m$ 就是计算的result。有 $n$ 个输入的boolean citrcuit计算了一个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$ 个辅助比特作为输出时，就可以定义由circuit计算多个输出的函数 $F:\mathbb{B}^n \rightarrow \mathbb{B}^m$ 。

电路也可以用无环有向图(Acyclic directed graph)表示。

Boolean circuits

其中最顶端in-degree是0的顶点代表输入；
其他顶点代表从basis中选出来的function，in-degree代表了输入这个函数的变量个数，match the arity of the function;
每一条进入顶点的边，都代表了一个变量的输入；
最下面的是输出顶点。
graph = assignments。二者可以互相转化。

Formula: 除了最后一个作为输出的辅助变量之外，其他的辅助变量都只用了一次。但是输入变量可以多次使用。Formula的graph可以用树来表示，叶子结点是输入，一个输入会出现多次。我们可以把一个formula表示成只有输入， $A$ 中的function和括号的表达式，且它的长度和assignments的长度差不多。如果是一般的boolean function，则长度可能会指数增长。

Complete basis: 基 $A$ 被称作完备的，如果任意boolean function $f$ ，都存在基 $A$ 上的circuit可以计算 $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:假设function取值为1的自变量只有一种，则它可以由literals的conjunction来计算；literals是 $x$ 或者 $\neg x$ 。例如 $f(x_1, x_2, x_3)$ 当 $x_1=1, x_2=0, x_3=1$ 时为真，则 $f(x_1, x_2, x_3)=x_1 \land \neg x_2 \land x_3.$
更一般的，一个函数 $f$ 可以表达为如下形式： $f(x) = \vee_{\{u: f(u)=1\}}\chi_u(x),$ 其中 $u$ 时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转化为CNF。

根据identities，basis{ $\neg, \vee, \land$ }是冗余的，只需要{ $\neg, \vee$ }或者{ $\neg, \land$ }就可以构成完备基(complete bases). { $\land, \oplus$ }也是完备基。

Circuit complexity

size of circuit: 一个circuit中assignments的数量。
circuit complexity of $f$ : 在基 $A$ 上的计算函数 $f$ 的circuit的最小(minimal) size，记为 $c_A(f)$ 。
此处的复杂度 $c_A(f)$ 和基 $A$ 的选取有关。但从一个有限基变换到另一个基，对复杂度的改变最多只是一个常数，所以有 $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.

对于一个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，非均匀，是说对不同的输入长度，都有一个boolean circuit的size是多项式的。

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

proof: 取 $F \in P$ ，证明 $F \in P/poly$ 。
对 $F$ 来说，存在图灵机 $M$ ，runs in polynomial time and space。对 $n$ 长的输入，step $T=poly(n)$ ，space $s=poly(n)$ ，所以可以拿一个space-time的图表来表示。

space-time diagram

其中每一个cell $\Gamma_{j,k}$ 记录了图灵机在 $j$ step， $k$ -th cell的symbol和图灵机的状态。因为symbol和状态都是有限且与 $n$ 无关的，所以这些状态可以编码成二进制串，长度与 $n$ 无关。由于每次head位移最多是1，所以每一个cell只由上面相邻三个决定。这个决定关系可以看作是一个boolean function，而且可以由circuit of size O(1)计算。把这些circuits组合起来形成一个大的circuit，把上面的space-time diagram算完，这个大的circuit的size是 $O(sT)O(1)=poly(n)$ 。
输入部分需要 $O(n)$ assignment，输出部分只要看第一个cell就可以， $O(1)$
。
总体来说，我们得到了一个 $\text{poly}(n)$ -size的circuit计算了Boolean function $F_n$ 。

Remark2.1 $P \neq P/poly$ ，也就是说 $P$ 是 $P/poly$ 的真子集。

举例：设 $\phi: \mathbb{N} \rightarrow \mathbb{B}$ 是任意函数。令predicate $F_\phi(x) = \phi(|x|)$ 。则 $(F_\phi(x))_n$ 是一个常数函数， $c((F_\phi(x))_n)=O(1)$ ，所以 $F_\phi \in P/poly$ for any $\phi$ 。但对于noncomputable的函数 $\phi$ 来说， $F_\phi$ 不可计算，不属于 $P$ 。

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

事实上，class $P/poly$ 相对来说很小：size为 $poly(n)$ 的circuit的数量不会超过 $O(((n+poly(n))^2)^{poly(n)}) = 2^{2poly(n)(log(poly(n))+O(1))} = 2^{poly(n)}.$ 而输入长度为 $n$ 的Boolean function共有 $2^{2^n}$ 个。uniform和nonuniform computation的不同对于更大的复杂性类中非常重要。

EXPTIME: the class of predicates decidable in time $2^{ploy(n)}$ ，是一个非平凡的可计算类。然而，把它类比到nonuniform之后，它就包含了所有的predicates.我们可以把所有的可能性编码到指数线路中。

定理2.3 Alternative P Theorem:

Predicate $F \in P$ 当且仅当如下条件成立：

$F \in P/poly$ ;
Boolean functions $F_n$ 由polynomial-size的circuits $C_n$ 计算时有如下性质：存在一个图灵机，对每一个正整数输入 $n$ (二进制编码，长度为 $\log(n)$ )，运行时间为 $poly(n)$ 并且构建了circuit $C_n$ 。

A 列满足上面性质的 $C_n$ 被称为polynomial-time uniform。
证明：左推右由定理2.2证明过程是显然的。
右推左，(不理解定理第二条里面图灵机是干什么的)。

经典计算：Lecture2 Boolean Circuits I

2 Boolean circuits

2.1 Definitions. Complete bases

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

Circuit complexity

2.2 Circuits versus Turing machines.

定义2.1 P/ploy(nonuniform P):

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

Remark2.1 $P \neq P/poly$ ，也就是说 $P$ 是 $P/poly$ 的真子集。

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

定理2.3 Alternative P Theorem:

猜你喜欢

热点阅读

经典计算：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:

猜你喜欢

热点阅读

定理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。