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".

StackExchange Computer Science Q#35822, answer score: 10