2

我正在阅读《算法导论》第三版这本书。定理 34.2 有一个证明(第 1059 页):

因为多项式时间算法决定的语言类别是多项式时间算法接受的语言类别的子集,所以我们只需证明如果 L 被多项式时间算法接受,它是由多项式时间决定的算法。令 L 为某个多项式时间算法 A 所接受的语言……(证明被省略)……因此 A 是决定L的多项式时间算法。

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

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

4

1 回答 1

0

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

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

于 2013-03-22T06:16:46.260 回答