2
我在看书< <算法简介> >，第三版。有定理的证明34.2（页1059）：复杂性类的属性P
因为类的多项式时间算法决定语言是类的语言通过多项式时间 算法接受的一个子集，我们只需要表明如果L被多项式时间算法接受，则它由多项式时间 算法决定。设L是语言一些多项式时间接受 算法的一个...（省略证明）......，因此A是多项式时间 算法决定 L.
我认为这意味着如果存在两个集合A和B，并且A是B的子集，并且元素x∈A，则证明x∈B。另外，据我所知，“由多项式时间算法决定的语言类别是多项式时间算法接受的语言类别的子集”。因此，这证明混淆了我......
证明从书中省略了，因为它是一个前奏，在这个水平上，甚至理论是，你很难在这一点上理解 – 2013-03-22 06:18:06