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

1. What does a deterministic reduction give about the hardness of the problem that a randomized reduction does not give?

2. 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$?

3. If we have only randomized reduction, is $X$ still an $\sf NP$-complete problem or could it have faster algorithms?

4. 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:

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

2. The consequence is that P$\neq$BPP, which is conjectured to be false.

3. NP-hardness is defined with respect to deterministic reductions.

4. We say that the problem is "NP-hard with respect to randomized reductions".

• Right. That was my interpretation. – Yuval Filmus Jan 1 '15 at 11:22
• You can ask the moderators there to migrate the question. But generally speaking, perhaps it would be a good idea to restrain yourself on asking questions, trying to answer them on your own for longer before asking them online. – Yuval Filmus Jan 1 '15 at 11:32
• This site cannot replace basic education on the topic. A good start would be reading some lecture notes on topics that interest you, though it's better to take formal courses with graded assignments. – Yuval Filmus Jan 1 '15 at 11:35
• Your question is probably too wide. But this discussion is becoming too long, and it's time to stop it. – Yuval Filmus Jan 1 '15 at 11:44
• Not necessarily: the problem could be harder than NP. – Yuval Filmus Jan 8 '15 at 12:34