gpt4 book ai didi

algorithm - 多项式时间 : Accepting and Decision Algorithms

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:18:48 26 4
gpt4 key购买 nike

<分区>

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

"For other Problems, such as Turing's Halting Problem, there exists an accepting algorithm, but no decision algorithm exists".

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

"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

"Because the class of languages decided by a polynomial-time algorithms, we need only show that if L is accepted by a polynomial-time algorithm, it is decided by a polynomial-time algorithm.".

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

但是如果我们可以构造这样一个算法,那么停机问题怎么可能有一个接受算法,而不是一个决策算法呢?

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com