原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
ts input x. The length of the input x is n, and the length of the certificate y is O(nk).
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
polynomial time, since each step of the construction takes polynomial time. ▪ The languag
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea