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

| cite | improve this answer | |
  • 1
    $\begingroup$ Right. That was my interpretation. $\endgroup$ – Yuval Filmus Jan 1 '15 at 11:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 1 '15 at 11:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 1 '15 at 11:35
  • 1
    $\begingroup$ Your question is probably too wide. But this discussion is becoming too long, and it's time to stop it. $\endgroup$ – Yuval Filmus Jan 1 '15 at 11:44
  • 1
    $\begingroup$ Not necessarily: the problem could be harder than NP. $\endgroup$ – Yuval Filmus Jan 8 '15 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.