如何理解下面的这句话？ Every algorithm (computer program)can be viewed as an execution of a mapping from a subset of t to for some alphabets and 2 A consistent input instance of the first language an output instance of the second language
如何理解下面的这句话？ A consistent input instance of the first language an output instance of the second language
什么是难问题？ 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,S)where is an alphabet and L CUC*.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)=0fx∈U-L(x年L. the word "decide" For many decision problems (L,U,>we assume U =*In that case we shall use the short notation (L,instead of (L,*S)
判定问题的形式化表达 Pay attention to the word “decide
以下两种形式是等价的 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)=0过x∈U-Lx走L). Problem (L,U,S) Input:Anx∈U. Output:"yes”ifx∈L, "no"otherwise
以下两种形式是等价的
问题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: