知识卡片
验证计算可展开成组合电路
对任意NP语言的多项式验证器A,把每一步配置转移表示为组合电路M,并串接T(n)份。
固定程序与实例x,只让证书y作为输入;电路输出即A(x,y)的接受位。
这是电路可满足性NP难证明的核心构造。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
The basic idea of the proof is to represent the computation of A as a sequence of configurations. As Figure 34.9 illustrates, consider each configuration as comprising a few parts: the program for A, the program counter and auxiliary machine state, the input x, the certificate y, and working storage. The combinational circuit M, which implements the computer hardware, maps each configuration ci to the next configuration ci+1, starting from the initial configuration c0. Algorithm A writes its output—0 or 1—to some designated location by the time it finishes executing. After A halts, the output value never changes. Thus, if the algorithm runs for at most T (n) steps, the output appears as one of the bits in cT(n). The reduction algorithm F constructs a single combinational circuit that computes all configurations produced by a given initial configuration. The idea is to paste together T (n) copies of the circuit M.