问复杂性类P的性质
EN

Stack Overflow用户

提问于 2013-03-22 03:07:13

回答 1查看 498关注 0票数 2

我正在读<>第三版的书。定理34.2有一个证明(第1059页)：

由于多项式时间算法所决定的语言类是多项式时间算法所接受的语言类的子集，所以我们只需要证明，如果L被多项式时间算法所接受，那么它就由多项式时间算法决定。设L是由某些多项式时间算法A.(省略了证明)接受的语言...and，因此A是决定L的多项式时间算法。

我认为这意味着，如果有两个集合A和B，A是B的子集，元素x∈A，这证明了x∈B。

此外，我理解“由多项式时间算法决定的语言类别是多项式时间算法所接受的语言类的子集”。所以这个证据让我困惑..。

发布于 2013-03-22 06:16:46

在计算复杂性理论中，P又称PTIME或DTIME(n^O(1))，是最基本的复杂性类之一。它包含了所有的决策问题，这些问题可以由一个确定性图灵机使用多项式的计算时间或多项式时间来解决。

来源：维基百科:P(复杂性)

票数 0

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

原文链接：

https://stackoverflow.com/questions/15562025

复制

相似问题

问复杂性类P的性质EN