Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-124/4/ii/solution
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 4 ii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
First suppose . Run the RP algorithm for and the RP algorithm for its complement with fresh random bits. If the first accepts, output one; if the second accepts, output zero; otherwise repeat. Neither output can be wrong, and on every input the appropriate algorithm accepts in each round with probability at least . The number of rounds is dominated by a geometric distribution of mean two, so this is an always-correct algorithm with polynomial expected running time.
Conversely, let be always correct when it halts and have expected running time at most . Run it for steps. Markov inequality givesAccept exactly when halts and outputs one; this is an RP algorithm for . Accepting exactly when it halts and outputs zero is an RP algorithm for the complement. Thereforeis equivalent to zero-error expected polynomial time.
New to topics? Read the docs here!