← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3714.b.3.b.3.b

电路规模受验证时间的多项式界

理解等级:高级

验证器在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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[65000,70000))。 - 结论依据:原文§34.3–34.4证明梗概与公式归约;图表或XHTML已核对,不补造省略的形式化细节。 - 原始内容:Since the algorithm runs for at most O ( n k ) 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 ( n k ), 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 ( n k ) copies of M , and hence it has size polynomial in n . The reduction algorithm F can construct C from x in