Given a problem X, to show it is is NP-complete, one usually shows a determinist

Question

Given a problem X, to show it is is NP-complete, one usually shows a deterministic reduction from an 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 NP-complete to X, however one can show there is no deterministic reduction from an NP-complete problem to X?

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

What does it mean for problem X if there is a randomized reduction from NP-complete problems? (Does it mean X is still NP-complete?)

Explanation / Answer

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?NP. The assumption BPP?NP does rule out polynomial time algorithms for any such problem, however

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.