Problems of Boolean Circuits

作者: richybai | 来源:发表于2022-03-23 19:15 被阅读0次

2.1 Is set a complete basis? Construct an algorithm that determines whether a given set of Boolean functions A constitutes a complete basis. (Functions are represented by tables.)

proof:

2.2 Maximum complexity. Let $c_n$ be the maximum complexity $c(f)$ for Boolean functions $f$ in $n$ variables. Prove that $1.99^n < c^n < 2.01^n$ for sufficiently large $n$ .

proof: 考察的是 $n$ 个变量的boolean function，要使它的复杂度达到最大，也就是尽可能的多用到变量。考虑total function，而且值都是1，它的DNF表达式为： $f(x) = \vee_{\{u \in \mathbb{B}^n\}}\chi_u(x)$
上界(upper bound)：根据DNF的表达式，每一个子函数，也就是conjunction的部分，是形如 $x_1 \land \neg x_2 \land \dots \land \neg x_n,$ 其中最多有 $2n$ 个operation；
在disjunction部分中，{ $u \in \mathbb{B}^n$ }共有 $2^n$ 个元素，所以 $c(f) = O(n2^n) < 2.01^n$ ， for large $n$ 。
下界(lower bound)：对比 $n$ 个变量的Boolean function和给定size大小的circuit的数量。假定选择了标准完备基，在k-th次assignment的时候，因为是从 $n$ 个输入变量和 $k-1$ 个辅助变量中选两个，最多有 $O((n+k)^2)$ 种可能性。所以size为 $s$ 的circuit的数量 $N_s$ 不会超过 $O(((n+s)^2)^s) = 2^{2s(log(n+s)+O(1))}.$ 而 $n$ 个变量的Boolean function的数量是 $2^{2^n}$ 个。如果 $2^n > 2s(log(n+s)+O(1)),$ 则Boolean function的数量比circuit的数量多，从而可以得到 $c_n > s$ 。因为 $s$ 是当输入为 $n$ 长时，上面不等式右侧那么多个circuit的最大的size，而 $n$ 长输入的Boolean function总共的数量是左侧的，所以肯定有别的Boolean function的复杂度比 $s$ 大，题干里说的是maximum complexity。或者就是对两边的集合里的元素取size的maximum，得到 $c_n > s$ 。
当 $s = 1.99^n$ 时，上述的不等式成立，for sufficiently large n。从而可以推出想要的不等式。