简单证明电路满足问题是NP-HARD

Question

$ newCommand { np} { Mathsf {np}} newCommand { cc} { textrm {circul-sat}} $我很难理解$ np $ - hardness for $ cc $ in $ cc $ in CLR.

$ cc = { langle c rangle：c text {是令人满意的组合布尔电路} } $

引理： $ cc $问题是$ mathsf {np} $ - 硬。

谁能提供易于理解的证据？

Answer 1

（非常）简化的版本是他们将任何验证算法$ a $转换为 text {np} $中的语言$ l $ a $。

他们最终得到的是一个电路$ c $，给定一个（二进制）字符串$ x $可满足（即$ c（x）= 1 $），并且仅当$ x in l $ in L $（即存在一个$ x ）证书$ y $，这样$ a（x，y）= 1 $）。

他们通过编码某些图灵机体现的算法（即过渡功能）作为电路$ m $所体现的算法的工作来做到这一点。然后，总电路$ c $是一系列$ m $的串联，其中每次迭代的输入值是$ m $的二进制二进制二进制编码，该状态体现了$ a $。

由于其中的每一位（包括$ a $ afting的步骤$）都以$ x $的大小为界，因此电路可以在多项式时间内构造。

因此，他们总体上给出的是构造模拟$ a $ a $ a $的电路的多项式时间，并且只有当我们能在l $中找到一些$ x 的证书时，这是令人满意的。然后，如果我们可以在多项式时间内决定如果满足$ c $，我们会知道有一些证书在l $中证明$ x ，因此在多项式时间内确定$ l $。