练习:问题的归约与不可解性
6.49 找到 37 703 491 的一个非平凡因数。
6.50 证明最短路径问题可以归约为线性规划问题。
6.51 如果 P ≠ NP,是否存在能够在
时间内解决某个 NP- 完全问题的算法?解释你的回答。
6.52 假设某人发明了一种保证能够在与
成正比的时间内解决布尔可满足性问题的算法。这说明我们能够在与
成正比的时间内解决其他 NP- 完全问题吗?
6.53 一个能够在与
成正比的时间内解决整数线性规划问题的程序的意义是什么?
6.54 给出一个从顶点覆盖问题向 0-1 整数线性不等式可满足性问题的多项式时间的归约。
6.55 使用无向图中的汉密尔顿路径问题的 NP- 完全性证明在 有向图 中寻找汉密尔顿路径的问题也是 NP- 完全的。
6.56 假设两个问题都已知是 NP- 完全的,这说明能够在多项式时间内将两者相互归约吗?
6.57 假设问题
是 NP- 完全的,
能够在多项式时间内归约为问题
,而且
也能在多项式时间内归约为
,那么
一定是 NP- 完全的吗?
答:不,因为
不一定属于 NP。
6.58 假设我们有一个能够解决布尔可满足性问题的确定性版本的算法,这说明存在某种变量赋值能够满足所有的布尔表达式。说明如何找到这种赋值方案。
6.59 假设我们有一个能够解决顶点覆盖问题的确定性版本的算法,这说明对于某个给定的大小存在顶点覆盖的方案。说明如何解决最小顶点覆盖问题的最优化版本。
6.60 解释为何顶点覆盖问题的最优化版本不一定是一个搜索问题。
答:因为并没有很好的方法来验证给定的节是否是最优的。(尽管我们可以用二分查找在这个问题的搜索版本上找到最优解。)
6.61 假设问题
和问题
均为搜索问题,且
能够在多项式时间内归约为
。我们可以得到以下哪些结论。
a. 如果
是 NP- 完全的,那么
也是。
b. 如果
是 NP- 完全的,那么
也是。
c. 如果
属于 P,那么
也属于 P。
d. 如果
属于 P,那么
也属于 P。
6.62 假设 P ≠ NP,我们可以得到以下哪些结论。
a. 如果问题
是 NP- 完全的,那么
无法在多项式时间内得到解决。
b. 如果问题
属于 NP,那么
无法在多项式时间内得到解决。
c. 如果问题
属于 NP 但并不是 NP- 完全的,那么
可以在多项式时间内得到解决。
d. 如果问题
属于 P,那么
就不是 NP- 完全的。
看完了
如果您对本书内容有疑问,可发邮件至contact@turingbook.com,会有编辑或作译者协助答疑。也可访问图灵社区,参与本书讨论。
如果是有关电子书的建议或问题,请联系专用客服邮箱:ebook@turingbook.com。
在这里可以找到我们:
- 微博 @图灵教育 : 好书、活动每日播报
- 微博 @图灵社区 : 电子书和好文章的消息
- 微博 @图灵新知 : 图灵教育的科普小组
- 微信 图灵访谈 : ituring_interview,讲述码农精彩人生
- 微信 图灵教育 : turingbooks