Randomized and deterministic reduction Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem.

If it is hard to show deterministic reduction, then one shows a randomized reduction.


What does a deterministic reduction give about the hardness of the problem that a randomized reduction does not give?
What is the consequence if there is a randomized reduction from an $\sf NP$-complete to $X$, however one can show there is no deterministic reduction from an $\sf NP$-complete problem to $X$?
If we have only randomized reduction, is $X$ still an $\sf NP$-complete problem or could it have faster algorithms?
What does it mean for problem $X$ if there is a randomized reduction from $\sf NP$-complete problems? (Does it mean $X$ is still $\sf NP$-complete?)
Let's answer your questions one by one:


A deterministic reduction proves NP-hardness. A randomized reduction doesn't. If a problem is NP-hard with respect to randomized reductions, then it could (potentially) be solvable in polynomial time even if P$\neq$NP. The assumption BPP$\neq$NP does rule out polynomial time algorithms for any such problem, however – even randomized ones.
The consequence is that P$\neq$BPP, which is conjectured to be false.
NP-hardness is defined with respect to deterministic reductions.
We say that the problem is "NP-hard with respect to randomized reductions".