《计算复杂性:现代方法》——2.2 归约和NP完全性
本节书摘来自华章计算机《计算复杂性:现代方法》一书中的第2章,第2.2节,作者 [美]桑杰夫·阿罗拉(Sanjeev Arora),博阿兹·巴拉克(Boaz Barak),译 骆吉洲,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.2 归约和NP完全性
我们怎样才能证明一个语言C至少与另外一个语言B一样难呢?归约的概念是我们完成这种任务的关键工具。
本节书摘来自华章计算机《计算复杂性:现代方法》一书中的第2章,第2.2节,作者 [美]桑杰夫·阿罗拉(Sanjeev Arora),博阿兹·巴拉克(Boaz Barak),译 骆吉洲,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
我们怎样才能证明一个语言C至少与另外一个语言B一样难呢?归约的概念是我们完成这种任务的关键工具。