4

如果我定义多时间函数，即图灵机可以在最大多项式（n）时间内计算的函数，其中 n 是输入的大小。这些函数的类是递归可枚举的吗？

4

3 回答 3

1

对在多项式时间内可计算的所有函数进行枚举相对容易：只需对所有多项式给出枚举 pi_j，对于 N 中的 j，然后考虑任何对 (i,j) 的机器，其工作方式类似于图灵机 M_i与时钟 pi_j。任何可在多项式时间内计算的函数都可以用这种方式表示。

这与理解通用图灵机是否在多项式时间内工作的问题有很大不同，这是不可判定的。这个证明并不完全是微不足道的，因为它不是程序的外延性质，我们不能应用赖斯定理。您可以在我的文章“莱斯定理的内涵内容”，POPL 2008（珍珠）中找到证明。

提供诸如 P、Pspace 等子递归复杂性类的句法表征的问题在文献中受到了广泛关注。最近的隐式复杂性领域旨在研究程序的计算复杂性，不参考特定的机器模型和时间或内存的明确界限，而是依赖逻辑或计算原则，这些原则需要复杂性属性，通常通过控制使用可用资源。有关该主题的介绍，您可以查阅关于隐式计算复杂性的特刊，ACM Trans。计算。日志，第 10 卷，2009 年第 4 期。

已经获得了其他有趣的特征，将编程语言的解释限制在有限域中。该领域的开创性成果是 Gurevich 的一项旧著作（“可行函数的代数”，FOCS 1983），他证明了在有限结构上解释原始递归函数（resp. recursive functions）可以精确地得到对数空间（resp.多项式时间）可计算函数。

请看我的文章“通过有限类型计算复杂性”，ACM Trans。计算。Log.，第 16 卷，2015 年第 15 期，有关该领域的更多参考资料。

于 2017-01-21T11:49:25.480 回答
0

我很确定答案是否定的。递归枚举 Poly-time 函数的程序必须在某些时候告诉您解决旅行商问题的函数是否是 Poly-time。该特定问题是否可以回答目前仍处于开放状态。

我不知道我在用那个可怕的答案抽什么。如果旅行商问题不是 Poly-time，则程序永远不必发现这个事实。它只需要永远列出任何解决方案。这很容易，因为它永远找不到。

我不清楚的一个重要细节是你如何表示函数，以及你认为什么是独特的函数。

假设该函数等于“在 Poly-time 中运行的程序”，并且您想列出所有程序，无论它们是否产生相同的输出。那么您的答案归结为：“如果给定程序是 Poly-time，则总有这个事实的证据吗？” 这显然是错误的。你可以有一个程序来搜索一个 poly time 来证明某个未解决的问题，如果找到它，它会在产生最终输出之前浪费指数级的时间。这个程序是多时间的，但你不能在不证明开放式问题是错误的情况下证明它。

假设您的函数等于“将输入与输出相关联的规则”，并且您不同意列出编码相同函数的多个程序。让我们修改之前的病理函数以修改其输出，而不是在发现所述证据时浪费时间。现在你可以证明这个程序是多时间的，但是你不能证明它是否代表了一个与不执行整个证明步骤（并且可能修改其输出）的函数不同的函数。

假设您的函数等于“将输入与输出相关联的规则”，并且您可以列出多个编码相同函数但不想要每个函数的程序。假设这prog是一个可能是或可能不是多时间并且p(x)是多项式的程序。很容易编写第二个程序来模拟第一个p(x)步骤，如果另一个程序仍在运行，则会发出一些固定的输出。这第二个程序保证是多时间的。如果实际上prog是多时间，那么这种形式的某些程序将表示相同的函数，prog因此输出列表将包括每个可能的多函数。（但相同的函数将以许多不同的方式编码。）

于 2011-02-16T15:54:41.503 回答
0

答案是肯定的，其实我也在书中找到了证明。谢谢大家，给了我很多帮助：）

于 2011-02-17T18:08:43.670 回答