多项式时间:接受和决策算法

Question

我似乎无法区分接受和决策算法,即使我觉得我理解这个概念.我目前正在阅读"算法简介"(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.

但是,如果我们可以构建这样的算法,那么停止问题怎么可能有接受但不是决策算法？

Answer 1

差异与运行时的上限有关.在考虑多项式时间算法时,如果您有多项式时间接受器,则可以将其转换为多项式时间决策器,如下所示:

• 在最坏的情况下运行算法以获得接受的多项式时间量.
• 如果它在这个时候接受了,太好了!接受.
• 如果它在这个时间不接受,它永远不会接受.拒绝.

因此,接受者可以变成决策者.

现在,考虑停止问题的同样事情:

• 只要在最坏的情况下接受算法就运行算法.
• 如果它在这个时候接受了,太好了!接受.
• 如果它在这个时间不接受,它永远不会接受.拒绝.

这里的问题是算法不会接受一些固定的时间 - 程序可以在接受之前任意运行很长时间,所以没有办法说"运行它直到它已经被接受",因为没有计算可以弄清楚这是什么时间的过程.

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

希望这可以帮助!