1
$\begingroup$

What is the formal definition of Random Reducibility>

Arora/Barak is like:

"yeah, so it's kind like you take an instance of a problem, create n random instances of the problem; and if you have the solution to those n instanes; then in polynomial time you can solve your original instance."

http://en.wikipedia.org/wiki/Random_self-reducibility

doesn't seem much better -- giving examples rather than a rigorous definition.

What is the rigorous definition of random self-reducibility? [And why do people tend to give hand wavey definitions?]

Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ Here is the definition from the Wikipedia article you have linked: "If a function $f$ evaluating any instance $x$ can be reduced in polynomial time to the evaluation of f on one or more random instances $y_i$, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction)." $\endgroup$
    – Kaveh
    Commented Sep 7, 2011 at 7:12
  • $\begingroup$ i.e. it is the same as self-reducibility, with the difference that instances in the self-reduction are chosen randomly. $\endgroup$
    – Kaveh
    Commented Sep 7, 2011 at 7:13
  • 3
    $\begingroup$ You first speak about random reducibility, and then random self-reducibility. It is not the same thing! Though I think your question really is about self-reducibility. $\endgroup$
    – Bruno
    Commented Sep 7, 2011 at 7:43
  • 1
    $\begingroup$ The Feigenbaum–Fortnow paper linked from the Wikipedia article (cs.uchicago.edu/~fortnow/papers/rsr.ps) has formal definitions on page 3. $\endgroup$
    – Emil Jeřábek
    Commented Sep 7, 2011 at 10:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .