Cheap and Secure Web Hosting Provider : See Now

# [Answers] Randomized and deterministic reduction

, ,
Problem Detail:

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?)

#### Answered By : Yuval Filmus

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