开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >PCP和停机问题的时间和空间复杂性

问PCP和停机问题的时间和空间复杂性
EN

Stack Overflow用户

提问于 2020-02-23 21:05:38

回答 1查看 68关注 0票数 0

因此，PCP是半可判定的和不可判定的，停顿问题也是不可判定的。有没有可能为它们命名一个时间复杂度，比如NP或expTime？

那么空间复杂性呢:它们是在Pspace中吗？

complexity-theory

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-02-25 22:50:41

因此，正如@walnut所说的那样，它们都不在提到的复杂性类中，因为这些类需要有一种算法来决定第一个place.Thank中的问题，以获得您的答案:)

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/60362485

复制

相似问题