← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

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

d on how the problem is encoded. Unfortunately, it depends quite heavily on the encoding.

For example, suppose that the sole input to an algorithm is an integer k, and suppose that the running time of the algorithm is Θ(k). If the integer k is provided in unary—a string of k 1s—then the running time of the algorithm is O(n) on length-n inputs, which is polynomial time. If the input k is provided using the more natural binary representation, however, then the input length is n = ⌊lg k⌋ + 1, so the size of the unary encoding is exponential in the size of the binary encoding. With the binary representation, the running time of the algorithm is Θ(k) = Θ(2n), which is exponential in the size of the input. Thus, depending on the encoding, the algorithm runs in either polynomial or superpolynomial time. The encoding of an abstract problem matters quite a bit to how we understand polynomial time. We cannot really talk about solving an abstract problem without first

specifying an encoding. Nevertheless, in practice, if we rule out “expensive” encodings s

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea