DEGREE BOUNDS ON POLYNOMIALS AND RELATIVIZATION THEORY

摘要

We demonstrate the applicability of the polynomial degree bound technique to notions such as the nonexistence of Turing-hard sets in some relativized world, (non)uniform gap-definability, and relativized separations. This way, we settle certain open questions of Hemaspaandra, Ramachandran & Zimand [HRZ95] and Fenner, Fortnow & Kurtz [FPK94], extend results of Hemaspaandra, Jain & Vereshchagin [HJV93] and construct oracles achieving desired results.