← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.780Z

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