原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
L ∪ L2 ∪ L3 ∪ …, where Lk is the language obtained by concatenating L to itself k times.
From the point of view of language theory, the set of instances for any decision problem Q is simply the set Σ*, where Σ = {0, 1}. Since Q is entirely characterized by those problem instances that produce a 1 (yes) answer, we can view Q as a language L over Σ = {0, 1}, where L = {x ∈ Σ* : Q(x) = 1}.
For example, the decision problem PATH has the corresponding language PATH = {〈G, u, v, k
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea