In this paper, we investigate an approach to circuit lower bounds via bounded width circuits. The approach consists of two steps: (i) We convert circuits to (deterministic or nondeterministic) bounded width circuits. (ii) We prove lower bounds for the bounded width circuits. For the second step, we prove that there is an explicit Boolean function $f$ as follows: If a nondeterministic circuit of size $s$ and width $w$ computes $f$, then $w = \Omega(\frac{n^4}{4^{\frac{s}{n}}s^3}) - \frac{\log_2 s}{2}$. For the first step, we give some observations, which include a relation between conversions to bounded width circuits and a standard pebble game.
翻译：在本文中，我们通过使用有限宽度电路研究了一种电路下限方法。该方法由两个步骤组成：（i）我们将电路转换为（确定性或非确定性的）有限宽度电路；（ii）我们为有限宽度电路证明下限。对于第二步，我们证明了一个显式的布尔函数$f$，如下：如果一个大小为$s$且宽度为$w$的非确定性电路计算$f$，则$w=\Omega(\frac{n^4}{4^{\frac{s}{n}}s^3})-\frac{\log_2 s}{2}$。对于第一步，我们给出了一些观察结果，它们包括将电路转换为有限宽度电路和标准卵石游戏之间的关系。
相关内容
微信扫码咨询专知VIP会员