再例： 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)
再例：
Existence of a solution of linear programming modulo p: ·What is the alphabet? {0,1,,p-1,#} ·What is the“existence"? SoL-IPp={(A,b)∈{0,1，，p-1,#}*lif A is an m×n matrix over Zp,m,n∈N-{o,andb∈Zr,then there exists X∈(Zp)"such that AX≡b(modp)}
Existence of a solution of linear programming modulo p: • What is the alphabet? • What is the “existence”?