ON COMPLETENESS UNDER RANDOM REDUCTIONS

In this paper, we study the notion of completeness under random reduct ions 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 approp riately high complexity classes where these questions do not have cont radictory relativizations. Our results show that the notion of complet eness under random reductions is sensitive to very small changes in su ccess probability, since we can separate completeness under reductions with very small differences in success probability. We also obtain op timal separations between completeness under various deterministic red uctions and random reductions. (C) 1996 Academic Press, Inc.