A comparison of weak completeness notions
Klaus Ambos‐Spies, Elvira Mayordomo, Xizhong Zheng · 2002
We compare the weak completeness notions for E in the sense of Lutz's resource-bounded measure theory (1992) with respect to the standard polynomial time reducibilities. Our results parallel results for classical completeness by Watanabe (1987) and others. We show that the weak completeness notions for 1-query reductions coincide: A set is weakly complete for E under 1-truth-table reducibility iff it is weakly complete for length-increasing one-one reducibility. For most of the other polynomial reducibilities, however, we obtain separations of the weak completeness notions where these reducibilities differ on E (Ladner et al. (1975)). In fact our separations simultaneously hold for the corresponding weak completeness notions for E and E/sub 2/, for the classical completeness notions, and for the weak completeness notions in the sense of the resource-bounded Baire category concepts of Ambos-Spies et al. (1988) and Ambos-Spies (1995).