问题3： ·算法A接受一个语言和算法A判定一个语言有什么区别？ The language accepted by an algorithm A is the set of strings L={xE(0,1)*:A(x)=13,that is,the set of strings that the algorithm accepts. A language L is decided by an algorithm A if every binary string in L is accepted by A and every binary string not in L is rejected by A. to accept a language,an algorithm need only produce an answer when provided a string in L,but to decide a language,it must correctly accept or reject every string in{0,1}
问题3： • 算法A接受一个语言和算法A判定一个语言有什么区别？
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' 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，并且是多项式时间算法
定理证明中有： 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，l}*:there exists y∈{0，l}*such that A(x,y)=l}
问题5：我们为什么要引入“多项式时间 验证”某个语言（问题）？