问题3：你能举一些类似的例子来帮助理 解“语言”的作用吗？ PRIM={w∈{0，l}*|Number(w)is a prime}. SAT=ww is a code of a satisfiable formula in CNF). CLIQUE={x#w∈{0，l,#}*|x∈{0,1}*and w represents a graph that contains a clique of size Number(c)}. VCP={u#w∈{0，l,#}+|u∈{0，l}f and w represents a graph that contains a vertex cover of size Number(u)
问题3：你能举一些类似的例子来帮助理 解“语言”的作用吗？
如何理解下面的这句话？ Every algorithm (computer program)can be viewed as an execution of a mapping from a subset of Si to 2 for some alphabets S1 and 2
如何理解下面的这句话？
什么是难问题？ We consider a problem to be hard if there is no known deterministic algorithm(computer program)that solves it efficiently. 我们将难问题分解为哪两类来研究？ decision problems◆→optimization problems
什么是难问题？ 我们将难问题分解为哪两类来研究？
判定问题的形式化表达 Definition 2.3.2.1.A decision problem is a triple (L,U,>where is an alphabet and L UC*.An algorithm A solves (decides)the decision problem (L,U,>if,for every x EU, ()A(x)=1fx∈L,amd Pay attention to ()A(x)=0讨x∈U-L(c年L). the word "decide" 问题5：如果x不在U中，怎么解释？ For many decision problems (L,U,D)we assume U=D*.In that case we shall use the short notation(L,∑)instead of(L,∑*，)
判定问题的形式化表达 Pay attention to the word “decide” 问题5：如果x不在U中，怎么解释？
以下两种形式是等价的？ Definition 2.3.2.1.A decision problem is a triple (L,U,>where is an alphabet and LU *An algorithm A solves (decides)the decision problem (L,U,>if,for every x EU, ()A(x）)=1fx∈L,amd ()A(x)=0fx∈U-L(x生L Problem (L,U, Input:Anx∈U. Output:"yes"ifx∈L, "no"otherwise
以下两种形式是等价的？