知识卡片
电路规模受验证时间的多项式界
验证器在T(n)=O(nᵏ)步内运行,证书和工作存储均为多项式规模;单步转移电路M的规模也受多项式界约束。
串接T(n)份M后,归约输出电路仍是多项式大小,因而可在多项式时间构造。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Since the algorithm runs for at most O(nk) steps, the amount of working storage required by A is polynomial in n as well. (We implicitly assume that this memory is contiguous. Exercise 34.3-5 asks you to extend the argument to the situation in which the locations accessed by A are scattered across a much larger region of memory and the particular pattern of scattering can differ for each input x.) The combinational circuit M implementing the computer hardware has size polynomial in the length of a configuration, which is O(nk), and hence, the size of M is polynomial in n. (Most of this circuitry implements the logic of the memory system.) The circuit C consists of O(nk) copies of M, and hence it has size polynomial in n. The reduction algorithm F can construct C from x in