On Completeness under Random Reductions

摘要

In this paper, we study the notion of completeness under random reductions and explore how that depends on the type and success probability of the reduction. We obtain absolute separations between completeness notions under various random reductions and between random reductions and deterministic reductions. These separations are obtained in appropriately high complexity classes where these questions do not have contradictory relativizations. Our results show that the notion of completeness under random reductions is sensitive tovery smallchanges in success probability, since we can separate completeness under reductions with very small differ- ences in success probability. We also obtain optimal separations between completeness under various deterministic reductions and random reductions.