为什么多项式时间语言具有多项式大小的电路？

Question

我想理解为什么P是PSCPACE的子集，这就是为什么多项式时间Langauge确实具有多项式大小的电路的原因。我读了很多证据 第2-3页, ，但是所有的证明都使用在库克乘法定理中使用的相同技术来将N位输入X上M的计算转换为多项式大小的电路。

我不明白的是，结果电路取决于输入X，因为要转换为电路的是在特定输入X上的M计算M。根据PSIZE的定义，相同的电路必须在固定长度的所有输入中工作，因此不取决于一个特定的输入。

那么，为多时间确定性图灵机创建多尺寸电路家族的过程如何完全起作用呢？

Answer 1

Cook-Levin为给定尺寸的所有输入提供了一个电路。因此，尽管电路取决于输入$ x $，但仅取决于输入的大小。因此，给定带有运行时间$ t $的TM $ m $，以及一个数字$ n $（输入的大小），库克 - levin给出了一个大小的电路$ c_n $，大约$ t^2 $，可以解决所有输入上的问题大小$ n $。电路$ c_n $不取决于$ m $的输入位，但是我们需要知道输入位的数量，因为这将是电路的输入位数。

Answer 2

直觉上，多项式大小问题至少需要多项式大小的电路，因为算法/电路中的每个步骤都需要一定的时间。如果电路可以在少于多项式时间内验证语言的元素，那么也可以制定算法。