计算机科学多项式时间归约本页总览多项式时间归约阐述 多项式时间可计算函数 一个函数 f:Σ∗→Σ∗f:\Sigma^*\to\Sigma^*f:Σ∗→Σ∗ 是一个多项式时间可计算函数，如果存在一个多项式时间的 Turing 机 MMM 对每个输入 www 停机且将 f(w)f(w)f(w) 写在条带上。 定义 语言 AAA 可多项式时间归约为 BBB（A≤PBA\le_PBA≤PB），如果存在一个多项式时间可计算函数 f:Σ∗→Σ∗f:\Sigma^*\to\Sigma^*f:Σ∗→Σ∗，对于每个 www 都有 w∈A⟺f(w)∈Bw \in A \Longleftrightarrow f(w) \in Bw∈A⟺f(w)∈B 推论 如果 A≤PBA\le_PBA≤PB 且 B∈PB\in PB∈P，则 A∈PA\in PA∈P 如果 B 是 NP 完全的，且 B≤PCB\le_PCB≤PC 对于某个 C∈NPC\in NPC∈NP，则 CCC 是 NP 完全的 实例 3SAT 可以多项式时间归约为 CLIQUE 性质 相关内容 参考文献