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. Our contributions are as follows. (a) There is a relativized world where AWPP has no polynomial-time Turing hard set for UP \cap coUP. This implies that classes like SPP, LWPP, WPP and AWPP do not possess Turing complete sets robustly; thus we answer an open question of [HRZ95] and extend one of the main results of [HJV93]. (b) There is a relativized world where AWPP has no polynomial-time Turing hard set for ZPP. (c) There is a relativized world where UP \cap coUP is not low for LWPP as well as for WPP. As a consequence, we show that both LWPP and WPP are not uniformly gap-definable. This settles an open question of [FFK94] and gives a relativized answer to another question of [FFK94]. (d) There is a relativized world where NP \cap coNP \nsubseteq AWPP. (e) There is a relativized world where ZPP is not contained in WPP^{WPP}. Thus WPP differs considerably from its superclass C_{=}P, for which it is known that PH \subseteq C_{=}P^{C_{=}P} in every relativized world. (f) Finally, we demonstrate that our proof technique is applicable also to classes that are not known to be gap-definable. We construct a relativized world where MIP \cap coMIP has no polynomial-time Turing hard set for ZPP. This extends one of the main results of [HJV93]