问题6：如何形式化描述一个decision problem (L,Σ) PRIMALITY TESTING Σ：∑bool L:PRIM ={w E(0,1]*Number(w)is a prime} Primality testing Input::Anx∈2tol Output:"yes"if Number(x)is a prime, "no"otherwise. 为什么书中要加这么一句话？ For primality testing we always consider(PRIM,Sooo)as the formal definition of this decision problem
问题6：如何形式化描述一个decision problem？ 为什么书中要加这么一句话？ ( L , ∑ ) ∑: ∑bool L:
再例： SATISFIABILITY PROBLEM. SAT={wwis a code of a satisfiable formula in CNF) CLIQUE PROBLEM CLIQUE={x#w∈{0，l,#}*|x∈{0，l}*and w represents a graph that contains a clique of size Number(x). VERTEX COVER PROBLEM Formally,the vertex cover problem (VCP)is the decision problem (VCP,10,1,#),where VCP={u#w∈{0，l,#}+|u∈{0，l}+and w represents a graph that contains a vertex cover of size Number(u)
再例：