Cheap and Secure Web Hosting Provider : See Now

[Answers] Randomized and deterministic reduction

, , No Comments
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?)

Asked By : Turbo

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback