1

我似乎无法区分接受算法和决策算法，尽管我觉得我确实理解了这个概念。我目前正在阅读“算法简介”（Cormen），并且在 NP-Completeness 章节之后遇到问题，因为它指出

“对于其他问题，例如图灵的停机问题，存在接受算法，但不存在决策算法”。

到目前为止，这对我来说确实有意义，但我们更进一步说

"P= {L from {0,1}*: there exists an algorithm A that decides L in polynomial time}

我们要证明 P 也是

P={L:L is accepted by a polynomial time algorithm}, starting with

“因为语言的类别是由多项式时间算法决定的，我们只需要证明，如果 L 被多项式时间算法接受，它就是由多项式时间算法决定的。”。

然后我们继续构建一个接受算法的模拟，它额外检查接受算法的行为，如果前一个算法接受输入，则输出 1，否则输出 0。

但是，如果我们可以构造这样的算法，Halting Problem 怎么可能有一个接受但没有一个决策算法呢？

4

1 回答 1

5

差异与运行时的上限有关。在考虑多项式时间算法时，如果您有多项式时间接受器，则可以将其转换为多项式时间判定器，如下所示：

  • 以多项式时间运行算法，在最坏的情况下接受它。
  • 如果它在这个时候接受，那就太好了！接受。
  • 如果它在这个时候不接受，它永远不会接受。拒绝。

因此，accepter可以变成decisioner。

现在，为停止问题考虑同样的事情：

  • 只要在最坏的情况下可以接受，就运行算法。
  • 如果它在这个时候接受，那就太好了！接受。
  • 如果它在这个时候不接受，它永远不会接受。拒绝。

这里的问题是算法接受并没有固定的时间量 - 程序可以在接受之前任意运行很长时间，所以没有办法说“运行它直到它已经接受”，因为没有计算可以弄清楚这是什么时间的过程。

有趣的是，它连接到 Busy Beaver 功能。直观地说，大小为 n 的忙碌海狸是一个长度为 n 的程序，它总是停止，但在所有大小为 n 的程序中需要最长的时间才能停止。对于特定的输入 w，n 阶 w 的繁忙海狸数是大小为 n 的繁忙海狸程序在输入 w 上停止所需要的步数。这个数字在数学上是明确定义的，但它不能由任何计算机程序计算，否则您可以使用它来使上述算法正常工作。

希望这可以帮助！

于 2014-02-12T21:15:28.783 回答