Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 3 iii Solution Created 2026-09-24 Updated 2026-09-25
Yes. The usual collapse relativizes because every machine involved receives the same oracle . Induct on the levels of the polynomial hierarchy. The hypothesis givesIf the preceding level is contained in , then its oracle queries can be simulated in polynomial time with oracle . A nondeterministic machine for the next existential level is therefore only an machine, hence a machine by hypothesis. Complements give the corresponding universal level. The induction yields