In fact,P is also the class of languages that can be accepted in polynomial time. Theorem 34.2 P={L:L is accepted by a polynomial-time algorithm}. •证明： ·为何我们只需证明被接受的语言（问题）一定可 以被判定？ ·How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A' 1)多项式算法A最多cnk步执行可以接受L的某个实例x 2)A'算法：接受任意的Σ*上的实例x,同样执行这cnk步，然后如果A接 受了x,A返回1，否则返回0 3)A'算法判定了L,并且是多项式时间算法•证明： •为何我们只需证明被接受的语言（问题）一定可 以被判定？ •How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A’ 1）多项式算法A最多cnk步执行可以接受L的某个实例x 2）A’算法：接受任意的Σ*上的实例x，同样执行这cnk步，然后如果A接 受了x，A’返回1，否则返回0 3）A’算法判定了L，并且是多项式时间算法