[26/M30] Let the Turing machine in Section 6.1.1 be probabilistic, which means that the machine can flip a fair coin to determine its next move.

(a) Assume that the machine is not allowed to err. Prove that such a machine still requires on average order n2 steps to accept the palindrome language L = {xxR : x ∈ {0, 1}∗}. The average is taken over the uniform distribution of all inputs of length n and all coin tosses of the algorithm.

(b) Assume that the machine is allowed to err with probability . Show that the palindrome language L can be accepted in worst-case time O(n log n) by such a machine.

Comments. Hint for Item (a): use the symmetry of information theorem, Theorem 2.8.2, on page 192. With high uniform probability, a sequence of random coin tosses r and a random input x are random relative to each other. Thus, the deterministic argument given in the proof of Section 6.1.1 proceeds as before with r as an extra input or oracle. Hint for Item (b): Generate random primes of size log n and check whether both sides are the same modulo these primes. Repeat this process to guarantee high accuracy. Source: [R. Freivalds, Information Processing 77, Proc. IFIP Congress 77, North-Holland, 1977, pp. 839–842].