2
我在看書< <算法簡介> >，第三版。有定理的證明34.2（頁1059）：複雜性類的屬性P
因爲類的多項式時間算法決定語言是類的語言通過多項式時間 算法接受的一個子集，我們只需要表明如果L被多項式時間算法接受，則它由多項式時間 算法決定。設L是語言一些多項式時間接受 算法的一個...（省略證明）......，因此A是多項式時間 算法決定 L.
我認爲這意味着如果存在兩個集合A和B，並且A是B的子集，並且元素x∈A，則證明x∈B。另外，據我所知，「由多項式時間算法決定的語言類別是多項式時間算法接受的語言類別的子集」。因此，這證明混淆了我......
證明從書中省略了，因爲它是一個前奏，在這個水平上，甚至理論是，你很難在這一點上理解 – 2013-03-22 06:18:06