Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-124/4/i/solution
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 4 i Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
A language belongs to RP when a polynomial-time randomized algorithm rejects every and accepts every with probability at least .
Amplify the algorithm on length- inputs with independent repetitions, accepting if any repetition accepts. Its error on each positive input is at most , while it still never accepts a negative input. Choose all random bits for all repetitions in advance. By the union bound, the probability that this one fixed choice fails on at least one of the at most positive strings is at mostThus some random string works simultaneously for every input of length . Hardwire that string into the polynomial-time computation and compile it into a Boolean circuit. The resulting polynomial-size circuit family decides , proving
New to topics? Read the docs here!