问题4：你能根据这个描述写出随机算法的图灵机模 型吗？ If one wants to formalize the notion of randomized algorithms,then one can take deterministic Turing machines A with an infinite additional tape.This additional tape is read-only;it contains an infinite random sequence of 0s and 1s,and A may move on it only from the left to the right.Another possibility is to take a nondeterministic Turing machine with nondeterministic guesses over at most two possibilities and to assign the probability to every such possibility
问题4：你能根据这个描述写出随机算法的图灵机模 型吗？
随机算法的概率空间 ·(SAx,Prob): SAx ={CIC is a computation of A onx}; Prob is a distribution over SAx, 什么意思？ Probax(C):it is 1/2 to the power of the number of random bits asked in C. Prob(A()=y),is the sum ofall Prob(C),where C outputsy
随机算法的概率空间 • 𝑆𝐴,𝑥, 𝑃𝑟𝑜𝑏 : • 𝑆𝐴,𝑥 = 𝐶 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴 𝑜𝑛 𝑥 ; 𝑃𝑟𝑜𝑏 𝑖𝑠 𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛 𝑜𝑣𝑒𝑟 𝑆𝐴,𝑥, • 𝑃𝑟𝑜𝑏𝐴,𝑥 𝐶 :𝑖𝑡 𝑖𝑠 Τ 1 2 𝑡𝑜 𝑡ℎ𝑒 𝑝𝑜𝑤𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑎𝑛𝑑𝑜𝑚 𝑏𝑖𝑡𝑠 𝑎𝑠𝑘𝑒𝑑 𝑖𝑛 𝐶. • Prob(A(x) = y), is the sum of all ProbA,x (C), where C outputs y. 什么意思？
随机算法设计日标 算法的输出是随机的 probability that A outputs y for an input x,Prob(A(x)=y),is the sum of all ProbA,(C),where C outputs y.Obviously,the aim of the randomized algorithm designer is to achieve high Prob(A(x)=y)if y is the correct output for the input x. S0
随机算法设计目标 算法的输出是随机的 So
问题5： 随机算法的期望时间复杂度和确定 算法的平均复杂度有什么不同？
问题5： 随机算法的期望时间复杂度和确定 算法的平均复杂度有什么不同？
For every randomized algorithm A we consider a new complexity measure- the number of random bits used.Let RandomA()be the maximum number of random bits used over all random runs (computations)of A on z.Then, for every n∈N, RandomA(n)=max {RandomA(x)is an input of size n}. 问题6： 这是什么意思？为什么品要这个定义？