◈练习:问题的归约与不可解性

练习:问题的归约与不可解性

6.49 找到 37 703 491 的一个非平凡因数。

6.50 证明最短路径问题可以归约为线性规划问题。

6.51 如果 P ≠ NP,是否存在能够在 N^{\log N} 时间内解决某个 NP- 完全问题的算法?解释你的回答。

6.52 假设某人发明了一种保证能够在与 1.1^N 成正比的时间内解决布尔可满足性问题的算法。这说明我们能够在与 1.1^N 成正比的时间内解决其他 NP- 完全问题吗?

6.53 一个能够在与 1.1^N 成正比的时间内解决整数线性规划问题的程序的意义是什么?

6.54 给出一个从顶点覆盖问题向 0-1 整数线性不等式可满足性问题的多项式时间的归约。

6.55 使用无向图中的汉密尔顿路径问题的 NP- 完全性证明在 有向图 中寻找汉密尔顿路径的问题也是 NP- 完全的。

6.56 假设两个问题都已知是 NP- 完全的,这说明能够在多项式时间内将两者相互归约吗?

6.57 假设问题 X 是 NP- 完全的,X 能够在多项式时间内归约为问题 Y,而且 Y 也能在多项式时间内归约为 X,那么 Y 一定是 NP- 完全的吗?

答:不,因为 Y 不一定属于 NP。

6.58 假设我们有一个能够解决布尔可满足性问题的确定性版本的算法,这说明存在某种变量赋值能够满足所有的布尔表达式。说明如何找到这种赋值方案。

6.59 假设我们有一个能够解决顶点覆盖问题的确定性版本的算法,这说明对于某个给定的大小存在顶点覆盖的方案。说明如何解决最小顶点覆盖问题的最优化版本。

6.60 解释为何顶点覆盖问题的最优化版本不一定是一个搜索问题。

答:因为并没有很好的方法来验证给定的节是否是最优的。(尽管我们可以用二分查找在这个问题的搜索版本上找到最优解。)

6.61 假设问题 X 和问题 Y 均为搜索问题,且 X 能够在多项式时间内归约为 Y。我们可以得到以下哪些结论。

a. 如果 Y 是 NP- 完全的,那么 X 也是。

b. 如果 X 是 NP- 完全的,那么 Y 也是。

c. 如果 X 属于 P,那么 Y 也属于 P。

d. 如果 Y 属于 P,那么 X 也属于 P。

6.62 假设 P ≠ NP,我们可以得到以下哪些结论。

a. 如果问题 X 是 NP- 完全的,那么 X 无法在多项式时间内得到解决。

b. 如果问题 X 属于 NP,那么 X 无法在多项式时间内得到解决。

c. 如果问题 X 属于 NP 但并不是 NP- 完全的,那么 X 可以在多项式时间内得到解决。

d. 如果问题 X 属于 P,那么 X 就不是 NP- 完全的。

看完了

如果您对本书内容有疑问,可发邮件至contact@turingbook.com,会有编辑或作译者协助答疑。也可访问图灵社区,参与本书讨论。

如果是有关电子书的建议或问题,请联系专用客服邮箱:ebook@turingbook.com。

在这里可以找到我们:

  • 微博 @图灵教育 : 好书、活动每日播报
  • 微博 @图灵社区 : 电子书和好文章的消息
  • 微博 @图灵新知 : 图灵教育的科普小组
  • 微信 图灵访谈 : ituring_interview,讲述码农精彩人生
  • 微信 图灵教育 : turingbooks