P类问题的定义： P=L 0,1*:there exists an algorithm A that decides L in polynomial time}. 问题4：这个定理，想表达什么？ Theorem 34.2 P={L:L is accepted by a polynomial-time algorithm}
P类问题的定义： 问题4：这个定理，想表达什么？
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' 多项式算法A=>最多cnk步执行=>将这cnk步看做算法A'=>A'可以在cnk内对输入x进行判定
•证明： •为何我们只需证明被接受的语言（问题）一定可 以被判定？ •How to do it? 用接受这个语言的算法A来构造判定这个语言的算法A’ 多项式算法A=>最多cnk步执行=>将这cnk步看做算法A’=>A’可以在cnk内对输入x进行判定
定理证明中有： If A has accepted x,then A'accepts x by outputting a 1.If A has not accepted x,then A'rejects x by outputting a 0. 这里面隐含了接受和判定的细微区别。你能解释一下吗？
定理证明中有： 这里面隐含了接受和判定的细微区别。你能解释一下吗？
问题5：我们为什么要引入“多项式时间 验证”某个语言（问题）？ We define a verification algorithm as being a two-argument algorithm A,where one argument is an ordinary input string x and the other is a binary string y called a certificate.A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x,y)=1.The language verified by a verification algorithm A is L={x∈{0，l1}*:there exists y∈0，l}*such that A(x,y)=}· 这里的所有概念，似乎都和问题复杂度，特别是超多项式复 杂度问题无关
问题5：我们为什么要引入“多项式时间 验证”某个语言（问题）？ 这里的所有概念，似乎都和问题复杂度，特别是超多项式复 杂度问题无关