用约束计数电路

Question

请原谅我如果这个问题是微不足道的，我就无法想出答案（也没有找到一个）。

为了表明有布尔函数 $ f：\ {0,1 \} ^ n \ lightarrow \ {0,1 \} $ 可以仅使用大小的电路 $ \ oomega（2 ^ n / n）$ ，我们使用一个计数参数：最多 $ O（2 ^ {k \ log k}）$ 大小的电路 $ k $ ， $ 2 ^ {2 ^ n} $ 这样的函数。

假设我对大小的计数电路感兴趣 $ k $ 计算不同的函数。 “简单”计数参数无法正常工作，因为可能有两个“句法”不同的电路实际上计算相同的功能。 换句话说，我想绑定集合的大小： $$ f={f：\ {0,1 \} ^ n \ lightarrow \ {0,1 \} | f \ text {可以使用大小电路计算} k \} $$

然后 $ | f | <$ 大小的电路数 $ k $ （由于任何电路计算一个函数），但我如何绑定 $ | f | $ 从下面？ （即 $ x <| f | $ ）

Answer 1

为了绑定由大小的电路计算的函数数 $ k $ ，您至少有两个选项：

• 构造大量大小的大量 $ k $ ，其通过施工计算不同的功能。
• 考虑大小的电路上的自然概率分布 $ k $ ，并估计两个随机电路计算相同功能的概率。

作为示例，已知 $ m $ 变量上的每个功能都可以由大小的电路 $ O（2 ^ m / m）$ 。通过考虑表单 $ f_1（x_1，\ ldots，x_m）\ lor \ cdots \ lor f_ {n / m}（x_ {n-m + 1}，\ ldots ，x_n）$ ，这表明至少存在 $（2 ^ {2 ^ m}）^ {n / m} $ 不同的功能计算按大小的电路 $ k= o（n2 ^ m / m ^ 2）$ 。在 $ k $ 方面，在 $ k \ log k $ 中，函数的数量大致是指数的。对于 $ m \ gg \ log n $ 。