原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
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